Online generalized assignment problem with historical information
New citation alert added.
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
![](http://writinghelp.online/777/templates/cheerup/res/banner1.gif)
New Citation Alert!
Please log in to your account
Information & Contributors
Bibliometrics & citations, view options, index terms.
Theory of computation
Design and analysis of algorithms
Approximation algorithms analysis
Scheduling algorithms
Online algorithms
Online learning algorithms
Theory and algorithms for application domains
Machine learning theory
Reinforcement learning
Sequential decision making
Recommendations
Online results for black and white bin packing.
In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
Improved lower bounds for the online bin packing problem with cardinality constraints
The bin packing problem has been extensively studied and numerous variants have been considered. The $$k$$ k - item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522---550, 1975 ). In addition to the formulation of the ...
Improved Online Algorithm for Fractional Knapsack in the Random Order Model
The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer ...
Information
Published in.
Elsevier Science Ltd.
United Kingdom
Publication History
Author tags.
- Online generalized assignment problem
- Online packing problem
- Historical information
- Random order model
- Competitive analysis
- Research-article
Contributors
Other metrics, bibliometrics, article metrics.
- 0 Total Citations
- 0 Total Downloads
- Downloads (Last 12 months) 0
- Downloads (Last 6 weeks) 0
View options
Login options.
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
Share this publication link.
Copying failed.
Share on social media
Affiliations, export citations.
- Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
- Download citation
- Copy citation
We are preparing your search results for download ...
We will inform you here when the file is ready.
Your file of search results citations is now ready.
Your search export query has expired. Please try again.
MS-0001-1922.65
Sample-Based Online Generalized Assignment Problem
Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals
Zihao Li, Hao Wang, Zhenzhen Yan \AFF School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, \EMAIL [email protected], \EMAIL [email protected], \EMAIL [email protected]
We study an edge-weighted online stochastic Generalized Assignment Problem with unknown Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline bin is associated with a D ๐ท D -dimensional capacity vector and each online item is with a D ๐ท D -dimensional demand vector which may be different towards each bin. Online arrivals are sampled from a set of online item types which follow independent but not necessarily identical Poisson processes. The arrival rate for each Poisson process is unknown. Each online item will either be packed into an offline bin which will deduct the allocated binโs capacity vector and generate a reward, or be rejected. The decision should be made immediately and irrevocably upon its arrival. Our goal is to maximize the total reward of the allocation without violating the capacity constraints.
We provide a sample-based multi-phase algorithm by utilizing both pre-existing offline data (named historical data) and sequentially revealed online data. We establish its performance guarantee measured by a competitive ratio. In a simplified setting where D = 1 ๐ท 1 D=1 and all capacities and demands are equal to 1 1 1 , we prove that the ratio depends on the number of historical data size and the minimum number of arrivals for each online item type during the planning horizon, from which we analyze the effect of the historical data size and the Poisson arrival model on the algorithmโs performance. We further generalize the algorithm to the general multidimensional and multi-demand setting, and present its parametric performance guarantee. The effect of the capacityโs (demandโs) dimension on the algorithmโs performance is further analyzed based on the established parametric form. Finally, we demonstrate the effectiveness of our algorithms numerically.
Sample-based Algorithm, Online Resource Allocation, Competitive Ratio
1 Introduction
Online Generalized Assignment Problem (GAP) is a fundamental research topic in resource allocation, which has been widely studied in various areas including operations research and computer scienceย Alaei etย al. ( 2013 ), Naori and Raz ( 2019 ), Albers etย al. ( 2020 ), Jiang etย al. ( 2021 ) . In this problem, we are given a set of offline bins with general capacities. During the online process, online items arrive in the system sequentially and request a certain bin capacity, name demand. Capacity and demand are in multi-dimensions and they can be different for different resources and requests. We need to pack the item into an offline bin with enough remaining capacity immediately and irrevocably upon its arrival or reject the item. If an item is packed into a bin, it consumes the binโs capacity by its demand and generates a reward. Our goal is to maximize the total reward of the output packing scheme.
This model has wide applications in various domains. Examples include online task assignment, ridesharing, and cloud computing.
Online task assignment. In some online task assignment platforms such as Amazon, the platform has several tasks to be allocated to a sequence of online arriving workers. Each task can be regarded as an offline bin and contains several processes. Each worker is regarded as an item with a single demand. Each worker arrives at the platform sequentially and takes one process in a task upon its arrival. A successful match of a worker to a task generates a reward that depends on the quality of the task completed by this worker.
Ridesharing. In a ridesharing platform such as Uber, each car can be regarded as a bin whose capacity is the number of guest seats in the car. Each ride request arrives at the platform in an online manner and requests some seats from a car nearby. A car can take multiple ride requests if the capacity permits. A successful match between a ride request and a car will generate a certain reward that depends on the carโs location and the passengerโs destination.
Cloud computing. In some commercial cloud computing services such as Azure and Google Cloud, multiple servers with different configurations are provided to agents. Agents arrive sequentially and request a certain amount of computing resources such as CPU and memory from a server. Allocating different servers to an agent may lead to different rewards depending on the serversโ configurations. The services providerโs goal is to maximize the total reward.
The general framework of the problem lends itself to a wide range of applications, but it also poses challenges when it comes to devising an efficient algorithm. Aggarwal etย al. ( 2011 ) demonstrated that no online algorithm can achieve a positive competitive ratio if the order of arrivals is determined by an adversary. However, if we assume that the arrivals follow a random order model, where the arriving order of online items is uniformly chosen from all possible permutations, Albers etย al. ( 2020 ) presented an online algorithm for the single-dimensional GAP that achieves a competitive ratio of 1 6.99 1 6.99 \frac{1}{6.99} . However, there is a scarcity of literature on the multi-dimensional GAP. To the best of our knowledge, Naori and Raz ( 2019 ) is the first one to provide an algorithm with a competitive ratio that depends on the dimensions under the random order arrival model. But there is no existing literature on the multi-dimensional GAP under a stochastic arrival model.
Poisson arrival is a widely-used stochastic arrival model. It has been extensively examined in various online problems (see Gamarnik and Squillante ( 2005 ), Jiang etย al. ( 2021 ), Yan ( 2022 ) ). In a typical Poisson arrival model, each online arrival of type v โ V ๐ฃ ๐ v\in V follows a Poisson process with a known arrival rate ฮป v subscript ๐ ๐ฃ \lambda_{v} . The arrival processes of different types are assumed to be independent. However, in many real-world scenarios, specific information regarding the arrival rates is often unavailable. In other words, the Poisson arrival rate for each type is unknown.
In this paper, we study an online stochastic multidimensional generalized assignment (GAP) problem in the context of an unknown Poisson arrival model. This study marks the initial endeavor to explore the online GAP in an unknown Poisson arrival setting. To tackle this problem, we leverage both the pre-existing offline data, referred to as historical data, and the sequentially-revealed online data, and develop an efficient multi-phase algorithm. Specifically, the algorithm includes a sampling phase to reject all arrivals and only collect arrival data, as well as several exploitation phases to allocate resources to online arrivals. The developed algorithm employs the concept of exploration-exploitation to dynamically learn the arrival rate and optimize the allocation decision. Through a thorough analysis of the algorithmโs performance, we examine the effect of the historical data size on the its effectiveness. Furthermore, we provide a novel insight on how to fine-tune the trade-off between exploration and exploitation in online algorithms based on the size of offline data as well as the time horizon.
We begin by considering a simplified setting of the GAP, where the dimension D = 1 ๐ท 1 D=1 and all capacities and demands are equal to 1 1 1 . In this simplified scenario, the problem reduces to a typical online bipartite matching where one side representing offline vertices and the other side representing online vertices. The online bipartite matching problem has received significant attention in the research community, with studies dating back to the seminal work by ย Karp etย al. ( 1990 ) , examining various arrival models. Karp etย al. ( 1990 ) studied the online matching under the worst-case model, i.e., the arrival sequence is determined by the adversary. Their goal is to maximize the number of successful matches. Kesselheim etย al. ( 2013 ), Zhang etย al. ( 2022 ) further studied a random order model and generalized the objective to maximize the total reward that is defined on the matched pairs. There is also a vast stream of literature that studies online bipartite matching under a known Poisson arrival modelย Feldman etย al. ( 2009 ), Manshadi etย al. ( 2012 ), Yan ( 2022 ) . In contrast, Section 3 in this paper studies this problem under a Poisson arrival model with unknown arrival rates. We develop an effective algorithm for the problem and demonstrate that the performance guarantee of the derived algorithm depends on two factors: the size of historical data and the minimum number of arrivals for each online item type throughout the planning horizon. In general, the algorithm achieves a higher ratio than the current state-of-the-art ratio of 1 e 1 ๐ \frac{1}{e} in the random order model ( Kesselheim etย al. ( 2013 ) ). As the size of the historical data grows sufficiently large, the ratio can reach the classical ratio of 1 โ 1 e 1 1 ๐ 1-\frac{1}{e} proposed by Feldman etย al. ( 2009 ) for the Poisson arrival model with known rates.
Next, we generalize the setting to the multidimensional GAP with general capacities and demands. We adopt a similar idea as described in Section 3 , which involves balancing exploration and exploitation, and develop another multi-phase algorithm. Remarkably, we prove that even in the absence of historical data, our algorithm can generate a better ratio than that achieved by Naori and Raz ( 2019 ) , the sole existing literature on online multidimensional GAP. The performance can get further improved by increasing the historical data size. When we skip specific phases in our algorithm, we propose two types of heuristic algorithms based on our main algorithm (see Sectionย 4.5.1 and Sectionย 4.5.2 ). By tuning the parameters of the heuristic algorithms, we further provide explicit forms of the competitive ratio.
1.1 Related Work
Online generalized assignment problem and its various simplified settings such as online bin packing and online knapsack problems have been studied extensively in the literatureย Alaei etย al. ( 2013 ), Naori and Raz ( 2019 ), Albers etย al. ( 2020 ), Jiang etย al. ( 2021 ) . Naori and Raz ( 2019 ) is a seminar work in studying the multidimensional GAP. They considered a random order model and showed that there exists O โ ( D ) ๐ ๐ท O(D) -competitive algorithms in the D ๐ท D -dimensional GAP, i.e., the competitive ratio of their algorithms is in the order of 1 D 1 ๐ท \frac{1}{D} . They also proved that the bound is tight in the order. Compared to our work, we adopt some ideas from their paper in designing our algorithm and prove that our algorithm can generate a better ratio than theirs under an unknown Poisson arrival model, even without any historical data.
3 superscript ๐ 2 0.319 \frac{1}{3+e^{2}}\approx 0.319 in both single-dimensional GAP and online knapsack problem. If the demand of each online item is also a random variable and its realization can only be observed after being packed into a bin, Alaei etย al. ( 2013 ) proposed an algorithm whose competitive ratio is 1 โ 1 k 1 1 ๐ 1-\frac{1}{\sqrt{k}} for the single-dimensional GAP assuming items arrive in an adversarial order. They assume that each itemโs demand is upper bound by 1 k 1 ๐ \frac{1}{k} fraction of the capacity of any bin and the distribution information for each possible arrival is known in advance.
Focusing on a simplified setting of the online single-dimensional GAP with the unit demand and capacity, the problem reduces to an online bipartite matching problem, which has received long-term attention from researchers. Karp etย al. ( 1990 ) started this stream of works and considered maximizing the total number of matches under the worst-case model. They presented an algorithm with a tight competitive ratio of 1 โ 1 e 1 1 ๐ 1-\frac{1}{e} . Manshadi etย al. ( 2012 ) followed this work and proposed an algorithm achieving a competitive ratio of 0.702 0.702 0.702 under a stochastic arrival process. Many follow-ups further study maximizing the vertex-weighted or edge-weighted matching under a random order arrival model or a stochastic arrival modelย Feldman etย al. ( 2009 ), Aggarwal etย al. ( 2011 ), Kesselheim etย al. ( 2013 ), Huang and Shu ( 2021 ), Huang etย al. ( 2022 ), Yan ( 2022 ), Feng etย al. ( 2023 ) . In particular, for maximizing the edge-weighted matching under the stochastic arrival model, Feldman etย al. ( 2009 ) proposed a linear-program-based Suggest Matching algorithm and showed that this algorithm can achieve a competitive ratio of 1 โ 1 e 1 1 ๐ 1-\frac{1}{e} . Their algorithm provides some intuitions for us in designing our algorithm in Sectionย 3 . Huang etย al. ( 2022 ) proposed a state-of-art algorithm under the vertex-weighted setting which achieves a competitive ratio of 0.716 0.716 0.716 and Feng etย al. ( 2023 ) proposed an algorithm with a competitive ratio of 0.650 0.650 0.650 under the edge-weighted setting when all arrivals follow a stochastic arrival process. Under the random order model, Kesselheim etย al. ( 2013 ) presented an algorithm that achieves a competitive ratio of 1 e 1 ๐ \frac{1}{e} , and showed this bound is tightย Mehta ( 2013 ) .
Another related stream of research is the online algorithms with samplesย Azar etย al. ( 2014 ), Correa etย al. ( 2019 ), Kaplan etย al. ( 2021 ), Zhang etย al. ( 2022 ) . Zhang etย al. ( 2022 ) is the most related one. In their paper, they studied a maximum edge-weighted matching under the random order model. They made use of the historical data in their matching algorithm and established the performance guarantee as a function of the size of historical data. Inspired by their algorithm, we design our three-phase algorithm for a simplified setting, where the dimension D = 1 ๐ท 1 D=1 and all the offline binsโ capacity and online itemsโ demand are one in Sectionย 3 . But note that we consider a Poisson arrival model while their work studied a random order model, which leads to a very different analysis of the performance guarantee. A concurrent work inย Liu etย al. ( 2023 ) also considers utilizing historical data in a multidimensional GAP problem. Compared to our work, their work considers the random order model and mainly focuses on two restricted settings where (1) dimension D = 1 ๐ท 1 D=1 , (2) the ratio between the capacity of the offline bin and the demand of the online item is upper bounded. Our work considers the general multidimensional GAP problem under the unknown Poisson arrival model, which has a great difference in the algorithm design and the analysis.
2 Preliminaries
We consider the following online stochastic generalized assignment problem (GAP), where we need to pack some online arriving items into some offline bins over a planning horizon of T ๐ T periods. We use U ๐ U to denote the set of bins. Each bin u โ U ๐ข ๐ u\in U is of D ๐ท D dimensions and has a capacity C u = ( C u 1 , โฆ , C u D ) โ โ โฅ 0 D subscript C ๐ข superscript subscript ๐ถ ๐ข 1 โฆ superscript subscript ๐ถ ๐ข ๐ท subscript superscript โ ๐ท absent 0 \textbf{C}_{u}=(C_{u}^{1},\ldots,C_{u}^{D})\in\mathbb{R}^{D}_{\geq 0} . We use V ๐ V to denote a set of item types, whose demand is of D ๐ท D dimensions. Packing an item whose type is v โ V ๐ฃ ๐ v\in V into a bin u โ U ๐ข ๐ u\in U consumes the capacity by r u โ v = ( r u โ v 1 , โฆ , r u โ v D ) โ โ โฅ 0 D subscript r ๐ข ๐ฃ superscript subscript ๐ ๐ข ๐ฃ 1 โฆ superscript subscript ๐ ๐ข ๐ฃ ๐ท subscript superscript โ ๐ท absent 0 \textbf{r}_{uv}=(r_{uv}^{1},\ldots,r_{uv}^{D})\in\mathbb{R}^{D}_{\geq 0} . We assume there are m ๐ m item types in V ๐ V . Packing an item of the type v โ V ๐ฃ ๐ v\in V into a bin u โ U ๐ข ๐ u\in U generates a non-negative reward of w u โ v subscript ๐ค ๐ข ๐ฃ w_{uv} . Without loss of generality, we assume each item can be packed into any bin. If a pair of item and bin is incompatible, we can simply set its rewards w u โ v subscript ๐ค ๐ข ๐ฃ w_{uv} to 0 0 . Our goal is to maximize the total reward of the packing without violating the capacity constraints of all bins. We formulate this GAP problem in mathematical form as follows,
max | (1) | ||||
s.t. | ( a) | ||||
( b) | |||||
( c) |
where n v subscript ๐ ๐ฃ n_{v} denotes the number of online arriving items of type v ๐ฃ v and x u โ v subscript ๐ฅ ๐ข ๐ฃ x_{uv} is the allocation decision, which represents the number of items of type v ๐ฃ v packed into the bin u ๐ข u .
We now define our online process. We are given a time horizon of T ๐ T and we assume T ๐ T is large, which is a standard assumption in the online resource allocation literature (e.g.,ย Feldman etย al. ( 2009 ), Huang and Shu ( 2021 ), Manshadi etย al. ( 2012 ), Jaillet and Lu ( 2014 ) ). We assume the online arrivals follow a type-specific Poisson process, i.e., the arrival rate of each item type v ๐ฃ v โs Poisson process denoted by ฮป v subscript ๐ ๐ฃ \lambda_{v} depends on its type. But ฮป v > 0 subscript ๐ ๐ฃ 0 \lambda_{v}>0 is unknown for all v โ V ๐ฃ ๐ v\in V . We assume each typeโs arrival process is independent from each other. Upon the arrival of one item, we need to make an immediate and irrevocable decision: pack it into one bin with enough space and generate a reward, or reject it.
Historical data. In this paper, we assume that the decision maker has some pre-existing offline data before the online process. We name them historical data in the subsequent presentation. We assume the historical data are generated from the same arrival model as in our online process in a time horizon of h โ T โ โ ๐ h\cdot T . In other words, the parameter h โ [ 0 , 1 ] โ 0 1 h\in[0,1] measures the size of the historical data. The number of each item type v ๐ฃ v in the historical data is around h โ T โ ฮป v โ ๐ subscript ๐ ๐ฃ hT\lambda_{v} .
Competitive ratio. We measure the performance of online algorithms by a competitive ratio. We define ALG( I ๐ผ I ) as the expected reward of the packing output by an online algorithm ALG on an instance I ๐ผ I of our problem. The expectation is taken over random arrivals of online items during the online planning horizon and the randomized (if needed) algorithm. We then compare its performance with a clairvoyant optimal algorithm OPT OPT \operatorname{{\textrm{OPT}}} , which holds the information of all the subsequent arrivals, i.e., each online arrivalโs type and its arriving time. We can similarly define OPT โก ( I ) OPT ๐ผ \operatorname{{\textrm{OPT}}}(I) as the expected reward of the packing output by OPT OPT \operatorname{{\textrm{OPT}}} on I ๐ผ I . For simplicity of the notion, we will call OPT โก ( I ) OPT ๐ผ \operatorname{{\textrm{OPT}}}(I) the offline optimal and drop I ๐ผ I when there is no ambiguity, in the following analysis. Then the competitive ratio of ALG is defined as the minimum ratio of ALG( I ๐ผ I ) over OPT โก ( I ) OPT ๐ผ \operatorname{{\textrm{OPT}}}(I) among all instances I ๐ผ I of our problem.
2.1 Important Lemmas
We next present two lemmas that help us analyze the performance of our algorithms, the proofs can be found in the appendix.
Lemma 2.1 (Number of Samples)
For a Poisson arrival process with an arrival rate ฮป > 0 ๐ 0 \lambda>0 during the time horizon of T ๐ T , and denote N = ฮป โ T ๐ โ ๐ ๐ N=\lambda\cdot T , we have that with probability 1 โ e โ N 8 1 superscript ๐ ๐ 8 1-e^{-\frac{N}{8}} , the number of arrivals n ๐ n is at least
Lemma 2.2 (Arrival Rate Estimation)
where ฮ = 4 โ ln โก 1 ฮด n ฮ 4 1 ๐ฟ ๐ \Delta=\sqrt{\frac{4\ln{\frac{1}{\delta}}}{n}} .
3 Online Matching
In this section, we consider a simplified setting of our model, where D = 1 ๐ท 1 D=1 and all the offline binsโ capacity and online itemsโ demand are 1 1 1 . Under this setting, the problem reduces to the traditional online edge-weighted bipartite matching, where one side is offline vertices and one side is online vertices. Thus, in the following of this section, we will call online items and offline bins online and offline vertices, respectively.
In this setting, we utilize some ideas behind some previous algorithms from Feldman etย al. ( 2009 ), Kesselheim etย al. ( 2013 ) and Zhang etย al. ( 2022 ) , which solve the online edge-weighted bipartite matching in a random order model or an unknown i.i.d. model. We then propose our algorithm, which is shown in Algorithmย 1 . Without loss of generality, we denote our online time horizon by [ 0 , T ) 0 ๐ [0,T) and the time horizon for historical data by [ โ h โ T , 0 ) โ โ ๐ 0 [-h\cdot T,0) . We define V โ ( [ a , b ) ) ๐ ๐ ๐ V([a,b)) as the set of online vertices arriving in the time interval [ a , b ) ๐ ๐ [a,b) . We then present a linear program (LP) denoted by L โ P โ ( ๐ , T ) ๐ฟ ๐ ๐ ๐ LP(\bm{\lambda},T) that will be used in the algorithm as follows. The decision variables are { x u โ v } subscript ๐ฅ ๐ข ๐ฃ \{x_{uv}\} .
max | (2) | ||||
s.t. | ( a) | ||||
( b) | |||||
( c) |
This LP is used in the Suggested Matching algorithm proposed by Feldman etย al. ( 2009 ) , which is used as part of our algorithm. From the proof of the Suggested Matching algorithm in Feldman etย al. ( 2009 ) , we get the following lemma.
The optimal value of L โ P โ ( ๐ , T ) ๐ฟ ๐ ๐ ๐ LP(\bm{\lambda},T) is an upper bound of the offline optimal in the online edge-weighted bipartite matching problem under known Poisson arrival model, where T ๐ T is the online time horizon and ๐ ๐ \bm{\lambda} represents the parameters of the type-specific arrivals.
We can now formally describe Algorithmย 1 . We reject all online arrivals and only collect samples for the arrival model in the first phase corresponding to the range [ 0 , ฮฑ โ T ) 0 โ ๐ผ ๐ [0,\alpha\cdot T) . We name it a sampling phase. After the sampling phase, we estimate the arrival rate ๐ ^ ^ ๐ \hat{\bm{\lambda}} and use it to advise our matching in the second phase, named a LP phase. Specifically, during the time interval [ ฮฑ โ T , ฮฒ โ T ) โ ๐ผ ๐ โ ๐ฝ ๐ [\alpha\cdot T,\beta\cdot T) , we allocate an offline vertex to each arriving vertex with a probability of ฮณ โ x ^ u โ v ฮป ^ v โ T โฒ โ ๐พ subscript ^ ๐ฅ ๐ข ๐ฃ subscript ^ ๐ ๐ฃ superscript ๐ โฒ \gamma\cdot\frac{\hat{x}_{uv}}{\hat{\lambda}_{v}T^{\prime}} , where ฮณ ๐พ \gamma is a scaling parameter and { x ^ u โ v } subscript ^ ๐ฅ ๐ข ๐ฃ \{\hat{x}_{uv}\} is the optimal solution of L โ P โ ( ๐ ^ , T โฒ ) ๐ฟ ๐ ^ ๐ superscript ๐ โฒ LP(\hat{\bm{\lambda}},T^{\prime}) . For the last phase corresponding to the time interval [ ฮฒ โ T , T ) โ ๐ฝ ๐ ๐ [\beta\cdot T,T) , we solve a deterministic matching problem in a bipartite graph which is formed by all the offline vertices on one side and the online arrivals during a time horizon of at most T ๐ T on the other side. We choose those arrivals in the following way: if the time horizon of previous arrivals (including the historical data and the online arrivals) is no more than T ๐ T , we use all the previous arrivals to form the bipartite graph, otherwise, we use the arrivals until time ( 1 โ h ) โ T 1 โ ๐ (1-h)T (including the historical data). We then apply the maximum bipartite matching algorithm to choose an offline resource for the arriving vertex. A match is made if the selected resource is available. We name the last phase a maximum matching phase.
The intuition behind our algorithm is as follows. We first reserve all the resources and only learn the arrival rate from the arrival data. After collecting a certain size of arrival data during the time interval [ 0 , ฮฑ โ T ) 0 โ ๐ผ ๐ [0,\alpha\cdot T) , we can estimate the arrival rate and perform the Suggested Matching algorithm using the estimated arrival rate to make the matching decision. Note that when the number of arrivals is very large, a deterministic matching is also known as a good matching algorithm. Hence we perform the maximum bipartite matching algorithm on the bipartite graph formed by the previous arrivals to guide our matching. We use a hyperparameter ฮฒ ๐ฝ \beta to determine whether we should perform this deterministic matching algorithm and when to perform it. If ฮฒ = 1 ๐ฝ 1 \beta=1 generates a better competitive ratio than all the other values (between 0 0 and 1 1 1 ), then it suggests that the Suggested Matching algorithm is sufficient for the matching. In fact, we find that a hybrid use of the Suggested Matching algorithm and the maximum bipartite matching can improve the performance according to our analysis of the competitive ratio.
Remark: The algorithms exhibits a trade-off of the exploration (collecting data to learn arrival rate) and exploitation (allocate resources to maximize expected reward). The longer the sampling period (i.e., the larger the ฮฑ ๐ผ \alpha ), the more focus on the exploration. This algorithm shares similar ideas to those for multi-armed bandit (MAB) problems. But we claim that the algorithms for MAB are not applicable to our problem due to the following reasons. First, we have limited capacity for each resource that is corresponding to each option in MAB. Hence we can only play each option limited times. In contrast, MAB allows each option to be played infinitely many times. Second, we are trying to learn the random arrival process instead of the random reward as in the MAB. Finally, in our problem the choice of the resource (option) is made based on the reward. In contrast, each option is played before knowing the reward in MAB.
Input : Online arrivals of agents, history arrivals h โ T โ โ ๐ h\cdot T Output : A feasible matching between online and offline vertices Parameter : Phase parameters ฮฑ ๐ผ \alpha , ฮฒ ๐ฝ \beta and scaling parameter ฮณ ๐พ \gamma satisfying 0 โค ฮฑ โค ฮฒ โค 1 0 ๐ผ ๐ฝ 1 0\leq\alpha\leq\beta\leq 1 and 0 โค ฮณ โค 1 0 ๐พ 1 0\leq\gamma\leq 1
We now analyze the performance of our algorithm. The analysis can be separated into two parts, for the LP phase and maximum matching phase, respectively.
3.1 LP phase
1 ฮ subscript ^ ๐ ๐ฃ (1-\Delta)\cdot\hat{\lambda}_{v}\leq\lambda_{v}\leq(1+\Delta)\cdot\hat{\lambda}_{v} holds, if there is no further specified.
We then can adopt the following two lemmas to bound the optimal value of L โ P โ ( ๐ ^ , T โฒ ) ๐ฟ ๐ ^ ๐ superscript ๐ โฒ LP(\hat{\bm{\lambda}},T^{\prime}) by OPT OPT \operatorname{{\textrm{OPT}}} and the probability of the successful matching in Stepย 12 , and conclude the expected reward during the LP phase by the third lemma below. The detailed proofs are deferred to appendix.
1 ฮ OPT \frac{1-\alpha}{1+\Delta}\operatorname{{\textrm{OPT}}} .
1 ฮ ๐ก ๐ผ ๐ 1 ๐ผ ๐ e^{-\gamma(1+\Delta)\frac{t-\alpha T}{(1-\alpha)T}} .
1 ฮ ๐ฝ ๐ผ 1 ๐ผ OPT (1-3\Delta)(1-\alpha)(1-e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}})\operatorname{{\textrm{OPT}}} .
3.2 Maximum matching phase
1 ฮ ๐ฝ ๐ผ 1 ๐ผ e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}} .
We assume one online vertex i ๐ i whose type is v โ V ๐ฃ ๐ v\in V arriving at time t โ [ ฮฒ โ T , T ) ๐ก ๐ฝ ๐ ๐ t\in[\beta T,T) , and โ โ \ell is the corresponding edge in the matching M โฒ superscript ๐ โฒ M^{\prime} (Stepย 20 in Algorithmย 1 ) which matches the corresponding type v ๐ฃ v of i ๐ i with one offline vertex. We first lower bound the expected weight of โ โ \ell . To do this, we first show that ๐ผ โ [ w โ ] โฅ ๐ผ โ [ ๐ผ [ OPT | | V | = k ] k ] {\mathbb{E}}[w_{\ell}]\geq{\mathbb{E}}[\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}|~{}|V|=k]}{k}] where the expectation is taken over k ๐ k and the set V ๐ V contains all arriving vertices in the time interval [ 0 , T ) 0 ๐ [0,T) . Based on this, we further use a function f โ ( x ) ๐ ๐ฅ f(x) to represent the corresponding value ๐ผ [ OPT | | V | = x ] {\mathbb{E}}[\operatorname{{\textrm{OPT}}}|~{}|V|=x] , and then show ๐ผ โ [ f โ ( x ) x ] โฅ ๐ผ โ [ f โ ( x ) ] ๐ผ โ [ x ] ๐ผ delimited-[] ๐ ๐ฅ ๐ฅ ๐ผ delimited-[] ๐ ๐ฅ ๐ผ delimited-[] ๐ฅ {\mathbb{E}}[\frac{f(x)}{x}]\geq\frac{{\mathbb{E}}[f(x)]}{{\mathbb{E}}[x]} to get the wanted conclusion. The details can be found in the appendix.
๐ผ โ [ w โ ] โฅ OPT T โ โ v โ V ฮป v ๐ผ delimited-[] subscript ๐ค โ OPT ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ {\mathbb{E}}[w_{\ell}]\geq\frac{\operatorname{{\textrm{OPT}}}}{T\sum_{v\in V}\lambda_{v}} .
Next, we need to bound the probability of the availability of the offline vertex u โ โ ๐ข โ u\in\ell .
We first consider the case when ฮฒ โ T โค t < ( 1 โ h ) โ T ๐ฝ ๐ ๐ก 1 โ ๐ \beta T\leq t<(1-h)T , i.e., V โฒ superscript ๐ โฒ V^{\prime} defined in Stepย 19 in our algorithm collects all previous online vertices during the total time horizon which is not greater than T ๐ T .
โ ๐ ๐ก e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}}\frac{(h+\beta)T}{hT+t} .
We next consider the case when ( 1 โ h ) โ T โค t < T 1 โ ๐ ๐ก ๐ (1-h)T\leq t<T , i.e., V โฒ superscript ๐ โฒ V^{\prime} collects only the online vertices arriving before time ( 1 โ h ) โ T 1 โ ๐ (1-h)T .
โ ๐ฝ superscript ๐ ๐ก 1 โ ๐ ๐ e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}}(h+\beta)e^{-\frac{t-(1-h)T}{T}} .
Using the similar ideas, we can conclude the following lemma for the case that ฮฒ > 1 โ h ๐ฝ 1 โ \beta>1-h .
1 ฮ ๐ฝ ๐ผ 1 ๐ผ superscript ๐ ๐ก ๐ฝ ๐ ๐ e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}}e^{-\frac{t-\beta T}{T}} .
We now can give the expected reward during the maximum matching phase compared to the offline optimal OPT OPT \operatorname{{\textrm{OPT}}} , by applying some calculus.
The expected reward during the maximum matching phase is at least:
The details of the above four lemmas can be found in appendix.
We then can summarize Lemmaย 3.4 and Lemmaย 3.9 and establish the performance of our algorithm in Theorem 3.10 .
Theorem 3.10
โ ๐ผ ๐ 8 1-m\delta-me^{\frac{-(h+\alpha)N}{8}} , Algorithmย 1 has a competitive ratio of at least:
โ ๐ผ ๐ \Delta=\sqrt{\frac{8ln\frac{1}{\delta}}{(h+\alpha)N}} .
We first compare the bound of competitive ratios at different h โ h and N ๐ N in Figureย 1(a) . From the figure, we first observe that when h โ h increases, our competitive ratio increases, which indicates that adding historical data indeed help improve our algorithmโs performance. Second, we also find that the value of N ๐ N also significantly affects the algorithmโs performance. Note that the value of N ๐ N reflects the quality of data measured by min v โ V โก ฮป v subscript ๐ฃ ๐ subscript ๐ ๐ฃ \min_{v\in V}\lambda_{v} for a fixed time horizon T ๐ T and the length of time horizon T ๐ T for a fixed arrival model. The dependence on N ๐ N indicates that when min v โ V โก ฮป v subscript ๐ฃ ๐ subscript ๐ ๐ฃ \min_{v\in V}\lambda_{v} is large for a given planning horizon, i.e., no item type is underrepresented, our algorithm performs well. It also suggests that for the same arrival process, we can improve the algorithmโs performance by expanding the online planning horizon.
We further compare the ratio with the state-of-art ratios in the literature. First, we see that most of the ratios are above 1 e 1 ๐ \frac{1}{e} , the state-of-art ratio for the random order modelย Kesselheim etย al. ( 2013 ) . It implies that incorporating the information on arrival model (Poisson arrival) can help improve the algorithmโs performance even when we have no information on its arrival rate, equivalently no historical data ( h = 0 โ 0 h=0 ). The value of the information is more signification when we have a longer planning horizon T ๐ T (corresponding to a larger N ๐ N for fixed arrival rates). Second, we find that when h โ h or N ๐ N is large enough, our ratio can reach 1 โ 1 e 1 1 ๐ 1-\frac{1}{e} , the ratio of the typical algorithm for known Poisson modelย Feldman etย al. ( 2009 ) . Finally, we can also compare the ratio with that derived by ย Zhang etย al. ( 2022 ) , which considers the same problem under a random order model with historical data. Since their algorithm is a special case of our algorithm where ฮฑ = ฮฒ ๐ผ ๐ฝ \alpha=\beta , the competitive ratio of our algorithm is always weakly better than that of their algorithm.
Finally, we discuss the optimal choices of hyperparameters ฮฑ ๐ผ \alpha and ฮฒ ๐ฝ \beta . We plot the optimal ฮฑ ๐ผ \alpha and ฮฒ ๐ฝ \beta at different h โ h and N ๐ N in Figures 1(b) and 1(c) , respectively. After fixing h โ h , we plot the portion of three phases under different N ๐ N in Figures 1(d) ,ย 1(e) and ย 1(f) . Similarly, after fixing N ๐ N , we also plot the portion of three phases under different choices of h โ h in Figures 1(g) ,ย 1(h) and ย 1(i) . In these six figures, the blue, green and red regions correspond to sampling phase, LP phase and the maximum matching, respectively.
For ฮฑ ๐ผ \alpha , from Figure 1(b) , we observe that when either h โ h or N ๐ N increases, the optimal ฮฑ ๐ผ \alpha decreases. It implies that when the historical data size increases, we can shorten the exploration period (sampling phase before the time point ฮฑ โ T ๐ผ ๐ \alpha T ) and exploit the decision earlier to get better performance. On the other hand, if the data quality is high, i.e., each item type has sufficient arrivals for us to learn its arrival rate, we can also shorten the exploration period. As shown in Figuresย 1(e) ,ย 1(f) ,ย 1(h) andย 1(i) , when h โ h and N ๐ N are large enough, i.e., a great amount of historical data, we can even ignore the sampling phase and initiate the exploration directly.
We then analyze the choice of the hyperparameter ฮฒ ๐ฝ \beta . From Figure 1(c) , we see that a larger ฮฒ ๐ฝ \beta is needed when N ๐ N increases or h โ h decreases. Note that when N ๐ N increases, the optimal ฮฑ ๐ผ \alpha decreases according to our earlier analysis. This concludes that more periods are reserved for the LP phase with fewer periods for maximum matching phase when N ๐ N increases. Such a trend can also be seen in Figures 1(d) ,ย 1(e) andย 1(f) . It implies that increasing data quality ( min v โ V โก ฮป v subscript ๐ฃ ๐ subscript ๐ ๐ฃ \min_{v\in V}\lambda_{v} ) can result in a more precise estimate of arrival rates and provide more substantial improvements in the LP phase compared to that in the maximum matching phase. Conversely, our analysis indicates that the performance of the maximum matching phase is primarily determined by the ratio of the historical data to the online data, as measured by h โ h . Thus, an increase in h โ h can improve the performance of the maximum matching phase more than that of the LP phase, which implies ฮฒ ๐ฝ \beta decreases with h โ h .
In addition, we observe that most choices of ฮฒ ๐ฝ \beta fall in the interval ( ฮฑ โ T , ( 1 โ h ) โ T ) ๐ผ ๐ 1 โ ๐ (\alpha T,(1-h)T) , which indicates that a hybrid use of LP and maximum matching algorithms can increase the performance guarantee in most cases.
![online generalized assignment problem Refer to caption](https://ar5iv.labs.arxiv.org/html/2302.08234/assets/x1.png)
We then consider a special case which allows us to give an explicit expression. If there is no historical sample, we can set ฮฒ = 1 ๐ฝ 1 \beta=1 and choose one ฮฑ ๐ผ \alpha such that 1 โ 3 โ ฮ = 1 โ ฮฑ 1 3 ฮ 1 ๐ผ 1-3\Delta=1-\alpha . In this case, we can achieve a relatively good performance guarantee.
Corollary 3.11
Denote N = min v โ V โก ฮป v โ T ๐ subscript ๐ฃ ๐ โ subscript ๐ ๐ฃ ๐ N=\min_{v\in V}\lambda_{v}\cdot T . Without historical samples ( h = 0 โ 0 h=0 ), for 0 < ฮด < 1 0 ๐ฟ 1 0<\delta<1 , with a probability of at least 1 โ m โ ฮด โ m โ e โ ฮฑ โ N 8 1 ๐ ๐ฟ ๐ superscript ๐ ๐ผ ๐ 8 1-m\delta-me^{\frac{-\alpha N}{8}} , Algorithmย 1 can achieve a competitive ratio with at least ( 1 โ 4 โ 9 โ l โ n โ 1 ฮด N 3 ) โ ( 1 โ 1 e ) 1 4 3 9 ๐ ๐ 1 ๐ฟ ๐ 1 1 ๐ \left(1-4\sqrt[3]{\frac{9ln\frac{1}{\delta}}{N}}\right)(1-\frac{1}{e}) by choosing ฮฑ = 72 โ l โ n โ 1 ฮด N 3 ๐ผ 3 72 ๐ ๐ 1 ๐ฟ ๐ \alpha=\sqrt[3]{\frac{72ln\frac{1}{\delta}}{N}} and ฮฒ = ฮณ = 1 ๐ฝ ๐พ 1 \beta=\gamma=1 .
When N ๐ N is large, we can conduct only the LP phase after sampling and get a competitive ratio close to 1 โ 1 e 1 1 ๐ 1-\frac{1}{e} , which is a good performance guarantee under our setting, compared to the well known ratio proposed in Feldman etย al. ( 2009 ) , which is 1 โ 1 e 1 1 ๐ 1-\frac{1}{e} under the known Poisson arrival setting.
4 Online Multidimensional GAP
In this section, we consider the online multidimensional GAP model. Adopting the ideas fromย Naori and Raz ( 2019 ) , we divide all edges between offline bins and online items into heavy edges and light edges according to the online itemโs demand vector, and design a multi-phase algorithm (see Algorithmย 2 ). In this section, because several lemmas have a similar proof in spirit to those in Sectionย 3 , we omit some proofs in this section and the details are deferred to the appendix. Before designing our algorithm, we first define the heavy and light edges as follows. For each bin u โ U ๐ข ๐ u\in U and each item type v โ V ๐ฃ ๐ v\in V , if r u โ v d โค 1 2 โ C u d superscript subscript ๐ ๐ข ๐ฃ ๐ 1 2 superscript subscript ๐ถ ๐ข ๐ r_{uv}^{d}\leq\frac{1}{2}C_{u}^{d} holds for all d โ [ D ] ๐ delimited-[] ๐ท d\in[D] , we call the edge ( u , v ) ๐ข ๐ฃ (u,v) a light edge, otherwise we call it a heavy edge. Intuitively, for a heavy edge ( u , v ) ๐ข ๐ฃ (u,v) , we cannot pack more than one item of type v ๐ฃ v into the bin u ๐ข u . We use โฐ H superscript โฐ ๐ป {\mathcal{E}}^{H} and โฐ L superscript โฐ ๐ฟ {\mathcal{E}}^{L} to represent the set containing heavy edges and light edges, respectively.
Following a similar idea as in Algorithmย 1 , we reserve some periods in the beginning of the time horizon as the sampling phase to only collect arrival data. In other words, we simply reject all arrivals in the sampling phase to collect data in the support of our estimation of arrival rates. In designing the exploitation phases, we note that packing light items may affect the packing of heavy items. To better utilize samples, we first deal with heavy edges. Hence the second phase is the heavy LP phase, where we will match some heavy edges according to the optimal solution of L โ P H โ ( ๐ ^ , T โฒ ) ๐ฟ superscript ๐ ๐ป ^ ๐ superscript ๐ โฒ LP^{H}(\hat{\bm{\lambda}},T^{\prime}) , where ๐ ^ ^ ๐ \hat{\bm{\lambda}} is an estimate of the model and T โฒ = ( 1 โ ฮฑ ) โ T superscript ๐ โฒ 1 ๐ผ ๐ T^{\prime}=(1-\alpha)T , as stated in Stepsย 6 - 7 of Algorithmย 2 . Here, T โฒ superscript ๐ โฒ T^{\prime} represents the total time horizon where we can consume the offline resources, i.e., excluding the sampling phase. We define L โ P H โ ( ๐ , T ) ๐ฟ superscript ๐ ๐ป ๐ ๐ LP^{H}(\bm{\lambda},T) as follows.
max | (3) | ||||
s.t. | ( a) | ||||
( b) | |||||
( c) |
In this LP, x u โ v subscript ๐ฅ ๐ข ๐ฃ x_{uv} is the decision variable representing the expected number of matches between bin u ๐ข u and item type v ๐ฃ v . Constraintsย ( 3 a ) bound the number of matches for each online type by its expected number of arrivals. Constraintsย ( 3 b ) bound the number of matches for each offline bin by the dimension D ๐ท D . This is because packing an item into a bin u ๐ข u in an heavy edge must break the conditions r u โ v d โค 1 2 โ C u d , d โ [ D ] formulae-sequence superscript subscript ๐ ๐ข ๐ฃ ๐ 1 2 superscript subscript ๐ถ ๐ข ๐ ๐ delimited-[] ๐ท r_{uv}^{d}\leq\frac{1}{2}C_{u}^{d},d\in[D] for at least a d โ [ D ] ๐ delimited-[] ๐ท d\in[D] . For each d โ [ D ] ๐ delimited-[] ๐ท d\in[D] , at most one item that break the condition r u โ v d โค 1 2 โ C u d superscript subscript ๐ ๐ข ๐ฃ ๐ 1 2 superscript subscript ๐ถ ๐ข ๐ r_{uv}^{d}\leq\frac{1}{2}C_{u}^{d} can be packed into the bin u ๐ข u . Therefore, at most D ๐ท D items in total can be packed into each bin if only considering heavy edges. Following the same reasoning for Lemmaย 3.1 , we have the following lemma.
The optimal value of L โ P H โ ( ๐ , T ) ๐ฟ superscript ๐ ๐ป ๐ ๐ LP^{H}(\bm{\lambda},T) is an upper bound of the offline optimal of the instance that only heavy edges can be matched under known Poisson arrival model, where T ๐ T is the online time horizon and ๐ ๐ \bm{\lambda} represents the parameters of the type-specific arrivals.
The third phase in Algorithmย 2 is named a heavy maximum matching phase, where only heavy edges can be matched. We adopt the similar algorithm as in the maximum matching phase in Algorithmย 1 in Sectionย 3 .
The fourth phase is the light LP phase, only light edges are considered. In this phase, we consider an LP relaxation of LPย ( 1 ) with the arrival rate ฮป ๐ \lambda , denoted by L โ P 0 L โ ( ๐ , T , C ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ๐ ๐ ๐ถ LP_{0}^{L}(\bm{\lambda},T,C) (see LPย ( 4 )). In this phase, we only consider the unused capacity of the offline resource and the remaining time horizon of ( 1 โ ฮท ) โ T 1 ๐ ๐ (1-\eta)T in this LP.
max | (4) | ||||
s.t. | ( a) | ||||
( b) | |||||
( c) |
The optimal value of L โ P 0 L โ ( ๐ , T , C ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ๐ ๐ ๐ถ LP_{0}^{L}(\bm{\lambda},T,C) is an upper bound of the offline optimal of the instance that only light edges can be matched under known Poisson arrival model where T ๐ T is the online time horizon, C ๐ถ C is the total capacity of offline bins and ๐ ๐ \bm{\lambda} represents the parameters of the type-specific arrivals.
The last phase is the light maximum packing phase. In this phase, only light edges can be matched. We define V โฒ superscript ๐ โฒ V^{\prime} as the set of all arrivals before time min โก { t , ( 1 โ h ) โ T } ๐ก 1 โ ๐ \min\{t,(1-h)T\} (including historical data). We use the solution ๐ ๐ \bm{y} of L โ P 1 L โ ( V โฒ ) ๐ฟ superscript subscript ๐ 1 ๐ฟ superscript ๐ โฒ LP_{1}^{L}(V^{\prime}) to decide the matching. We define L โ P 1 L โ ( V โฒ ) ๐ฟ superscript subscript ๐ 1 ๐ฟ superscript ๐ โฒ LP_{1}^{L}(V^{\prime}) as follows, where decision variables are { y u โ v } subscript ๐ฆ ๐ข ๐ฃ \{y_{uv}\} .
max | (5) | ||||
s.t. | ( a) | ||||
( b) | |||||
( c) |
Comparing this LP to LPย ( 1 ), we notice that this LP provides an upper bound of the instance that only light edges can be matched since we only relax the integral constraints of decision variables. Further, compared to LPย ( 4 ), the capacity C ๐ถ C here represents the total capacity, while the capacity in LPย ( 4 ) represents the unused capacity given by the parameter C ๐ถ C of the function L โ P 0 L โ ( ๐ , T , C ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ๐ ๐ ๐ถ LP_{0}^{L}(\bm{\lambda},T,C) .
We summarize the general idea behind our algorithm as follows. We first adopt a similar algorithm as Algorithmย 1 in Sectionย 3 to match the heavy edges, and then utilize the previous arrivals to guide the matching decision for the light edges in the last two phases for matching light edges. Here, since there are two LP phases for matching heavy and light edges, respectively, we set two scaling parameters ฮณ ๐พ \gamma and ฮณ โฒ superscript ๐พ โฒ \gamma^{\prime} to tune the corresponding matching probability in these two phases.
We next proceed to analyze the performance guarantee of this algorithm. Before we start the analysis for each phase, we first present two needed concepts: OPT H superscript OPT ๐ป \operatorname{{\textrm{OPT}}}^{H} and OPT L superscript OPT ๐ฟ \operatorname{{\textrm{OPT}}}^{L} . For an instance of our problem, we use OPT H superscript OPT ๐ป \operatorname{{\textrm{OPT}}}^{H} to represent the expected reward of the offline optimal if only heavy edges can be matched. OPT L superscript OPT ๐ฟ \operatorname{{\textrm{OPT}}}^{L} is the expected reward of the offline optimal if we can only match light edges. Then, the following lemma holds, since we can directly separate the offline optimal for the original instance into two solutions, where each one contains only heavy or light edges.
superscript OPT ๐ป superscript OPT ๐ฟ OPT \operatorname{{\textrm{OPT}}}^{H}+\operatorname{{\textrm{OPT}}}^{L}\geq\operatorname{{\textrm{OPT}}} .
Input : Online arrivals of agents, history arrivals h โ T โ โ ๐ h\cdot T Output : A feasible matching between online and offline vertices Parameter : Phase parameters ฮฑ ๐ผ \alpha , ฮฒ ๐ฝ \beta , ฮท ๐ \eta , ฮธ ๐ \theta ,and scaling parameters ฮณ ๐พ \gamma and ฮณ โฒ superscript ๐พ โฒ \gamma^{\prime} satisfying 0 โค ฮฑ โค ฮฒ โค ฮท โค ฮธ โค 1 0 ๐ผ ๐ฝ ๐ ๐ 1 0\leq\alpha\leq\beta\leq\eta\leq\theta\leq 1 and 0 โค ฮณ , ฮณ โฒ โค 1 formulae-sequence 0 ๐พ superscript ๐พ โฒ 1 0\leq\gamma,\gamma^{\prime}\leq 1
4.1 Heavy LP Phase
1 ฮ subscript ^ ๐ ๐ฃ (1-\Delta)\cdot\hat{\lambda}_{v}\leq\lambda_{v}\leq(1+\Delta)\cdot\hat{\lambda}_{v} in the following of the section, if there is no further specification.
1 ฮ superscript OPT ๐ป \frac{1-\alpha}{1+\Delta}\operatorname{{\textrm{OPT}}}^{H} .
1 ฮ ๐ก ๐ผ ๐ 1 ๐ผ ๐ ๐ท e^{-\gamma(1+\Delta)\frac{t-\alpha T}{(1-\alpha)T}D} .
For notation convenience, we let q ฮฑ ฮฒ superscript subscript ๐ ๐ผ ๐ฝ {q_{\alpha}^{\beta}} the lower bound of the probability that an offline bin u ๐ข u contains no item at the end of heavy LP phase in the following definition.
Definition 4.6
1 ฮ ๐ฝ ๐ผ 1 ๐ผ ๐ท {q_{\alpha}^{\beta}}=e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}D} .
The expected reward during the heavy LP phase is weakly larger than f ฮฑ ฮฒ โ OPT H โ superscript subscript ๐ ๐ผ ๐ฝ superscript OPT ๐ป f_{\alpha}^{\beta}\cdot\operatorname{{\textrm{OPT}}}^{H} where f ฮฑ ฮฒ = 1 D โ ( 1 โ 3 โ ฮ ) โ ( 1 โ ฮฑ ) โ ( 1 โ q ฮฑ ฮฒ ) superscript subscript ๐ ๐ผ ๐ฝ 1 ๐ท 1 3 ฮ 1 ๐ผ 1 superscript subscript ๐ ๐ผ ๐ฝ f_{\alpha}^{\beta}=\frac{1}{D}(1-3\Delta)(1-\alpha)(1-{q_{\alpha}^{\beta}}) .
The proof of the previous lemmas can follow the same techniques used in the proof for the corresponding lemmas in the analysis of the LP phase in Sectionย 3 .
4.2 Heavy Maximum Matching Phase
We next analyze the heavy maximum matching phase, which can also adopt a similar analysis as in the maximum matching phase of Algorithmย 1 in Sectionย 3 .
๐ผ โ [ w โ ] โฅ OPT H D โ T โ โ v โ V ฮป v ๐ผ delimited-[] subscript ๐ค โ superscript OPT ๐ป โ ๐ท ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ {\mathbb{E}}[w_{\ell}]\geq\frac{\operatorname{{\textrm{OPT}}}^{H}}{D\cdot T\sum_{v\in V}\lambda_{v}} .
To prove this lemma, the only difference from the proof of Lemmaย 3.5 is that we do not directly compare to the value OPT H superscript OPT ๐ป \operatorname{{\textrm{OPT}}}^{H} but compare to the optimal matching (each bin can be only packed one item). We assume the expected value of the latter term is OPT โฒ superscript OPT โฒ \operatorname{{\textrm{OPT}}}^{\prime} . Since there are at most D ๐ท D items in one bin, OPT H superscript OPT ๐ป \operatorname{{\textrm{OPT}}}^{H} can be upper bounded by D โ OPT โฒ โ ๐ท superscript OPT โฒ D\cdot\operatorname{{\textrm{OPT}}}^{\prime} , and we get the result.
โ ๐ ๐ก {q_{\alpha}^{\beta}}\cdot\frac{(h+\beta)T}{hT+t} .
โ ๐ฝ superscript ๐ ๐ก 1 โ ๐ ๐ {q_{\alpha}^{\beta}}(h+\beta)e^{-\frac{t-(1-h)T}{T}} .
If ฮฒ > 1 โ h ๐ฝ 1 โ \beta>1-h , when ฮฒ โ T โค t < ฮท โ T ๐ฝ ๐ ๐ก ๐ ๐ \beta T\leq t<\eta T , the probability of the event E ๐ธ E that bin u ๐ข u is not packed any item before time t ๐ก t is at least q ฮฑ ฮฒ โ e โ t โ ฮฒ โ T T superscript subscript ๐ ๐ผ ๐ฝ superscript ๐ ๐ก ๐ฝ ๐ ๐ {q_{\alpha}^{\beta}}e^{-\frac{t-\beta T}{T}} .
We define the lower bound of the probability that u ๐ข u is not packed any item during heavy maximum matching phase as below.
Definition 4.12
The probability of the event E ๐ธ E that bin u ๐ข u is not packed any item during heavy maximum matching phase is at least
The expected reward during the heavy maximum matching phase is at least q ฮฑ ฮฒ โ f ฮฒ ฮท โ OPT H โ superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ superscript OPT ๐ป {q_{\alpha}^{\beta}}f_{\beta}^{\eta}\cdot\operatorname{{\textrm{OPT}}}^{H} , where f ฮฒ ฮท superscript subscript ๐ ๐ฝ ๐ f_{\beta}^{\eta} is defined as:
The proof of the above lemmas can follow the same ideas as in the proof for the maximum matching phase in Sectionย 3 .
4.3 Light LP Phase
โ ๐ ๐ \Delta^{\prime}=\sqrt{\frac{8ln\frac{1}{\delta}}{(h+\eta)N}} . We next can lower bound the expected value of L โ P 0 L โ ( ๐ ^ , T โฒ , C ยฏ ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ^ ๐ superscript ๐ โฒ ยฏ ๐ถ LP_{0}^{L}(\hat{\bm{\lambda}},T^{\prime},\bar{C}) used in this phase by some fraction of OPT L superscript OPT ๐ฟ \operatorname{{\textrm{OPT}}}^{L} , through constructing the corresponding feasible solution for L โ P 0 L โ ( ๐ ^ , T โฒ , C ยฏ ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ^ ๐ superscript ๐ โฒ ยฏ ๐ถ LP_{0}^{L}(\hat{\bm{\lambda}},T^{\prime},\bar{C}) by the optimal solution for L โ P 0 L โ ( ๐ , T , C ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ๐ ๐ ๐ถ LP_{0}^{L}(\bm{\lambda},T,C) , whose value is exactly OPT L superscript OPT ๐ฟ \operatorname{{\textrm{OPT}}}^{L} .
1 superscript ฮ โฒ superscript OPT ๐ฟ {q_{\alpha}^{\beta}}q_{\beta}^{\eta}\frac{1-\eta}{1+\Delta^{\prime}}\operatorname{{\textrm{OPT}}}^{L} .
Then, for an offline bin u ๐ข u , we call it available if the consumption of this bin in each dimension does not exceed a half of the corresponding capacity. That is, if one bin is available at time t ๐ก t , this bin can accept any one item with light edge. By applying union bound and Markovโs inequality, we can obtain the following lemma.
1 superscript ฮ โฒ ๐ก ๐ ๐ 1 ๐ ๐ 1-2D\gamma^{\prime}(1+\Delta^{\prime})\frac{t-\eta T}{(1-\eta)T} .
Now we give the lower bound of expected reward during this phase, by adopting Lemmasย 4.14 andย 4.15 and integrating the expected reward for each possible time t ๐ก t during this phase.
The expected reward during the light LP phase is at least q ฮฑ ฮฒ โ q ฮฒ ฮท โ f ฮท ฮธ โ OPT L โ superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ superscript subscript ๐ ๐ ๐ superscript OPT ๐ฟ {q_{\alpha}^{\beta}}q_{\beta}^{\eta}f_{\eta}^{\theta}\cdot\operatorname{{\textrm{OPT}}}^{L} , where f ฮท ฮธ superscript subscript ๐ ๐ ๐ f_{\eta}^{\theta} is defined as below:
4.4 Light Maximum Packing Phase
We will analyze the performance during the light maximum packing phase in this subsection. According to the analysis of previous phase, the probability of the event E that a bin u ๐ข u has not been packed any items before time ฮท โ T ๐ ๐ \eta T is at least q ฮฑ ฮฒ โ q ฮฒ ฮท superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ {q_{\alpha}^{\beta}}q_{\beta}^{\eta} .
We assume one online vertex i ๐ i with type v โ V ๐ฃ ๐ v\in V arrives in the system at time t โ [ ฮธ โ T , T ) ๐ก ๐ ๐ ๐ t\in[\theta T,T) , and โ = ( u , i ) โ ๐ข ๐ \ell=(u,i) is the corresponding edge decided by Stepย 34 in Algorithmย 2 . We first lower bound the expected weight of โ โ \ell . The ideas behind the proofs can follow the proof of Lemmaย 3.5 , where the function f โ ( x ) ๐ ๐ฅ f(x) here should represent the expected value of L โ P 1 L ๐ฟ superscript subscript ๐ 1 ๐ฟ LP_{1}^{L} instead of the corresponding expected value of the optimal matching given the total number of arrivals x ๐ฅ x .
๐ผ โ [ w โ ] โฅ OPT L T โ โ v โ V ฮป v ๐ผ delimited-[] subscript ๐ค โ superscript OPT ๐ฟ ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ {\mathbb{E}}[w_{\ell}]\geq\frac{\operatorname{{\textrm{OPT}}}^{L}}{T\sum_{v\in V}\lambda_{v}} .
Next we can bound the probability of the event that corresponding match is successful.
Definition 4.18
1 superscript ฮ โฒ ๐ ๐ 1 ๐ q_{\eta}^{\theta}=\gamma^{\prime}(1+\Delta^{\prime})\frac{\theta-\eta}{1-\eta} .
When ฮธ โ T โค t < T ๐ ๐ ๐ก ๐ \theta T\leq t<T , the probability of the event E ๐ธ E that โ โ \ell can be chosen successfully conditioning on u ๐ข u is not packed by any item before ฮท โ T ๐ ๐ \eta T is at least
To prove this lemma, we can do the case study and apply the union bound and Markovโs inequality for each case to get the conclusion.
Remark: Because of the use of union bound, the above lower bound of the probability of the event E ๐ธ E may be negative, but this will not affect the following analysis, since this is still a feasible lower bound.
From some calculus, we can show the following lemma.
The expected reward during the light maximum packing phase is at least q ฮฑ ฮฒ โ q ฮฒ ฮท โ f ฮธ 1 โ OPT L โ superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ superscript subscript ๐ ๐ 1 superscript OPT ๐ฟ {q_{\alpha}^{\beta}}q_{\beta}^{\eta}f_{\theta}^{1}\cdot\operatorname{{\textrm{OPT}}}^{L} where f ฮธ 1 superscript subscript ๐ ๐ 1 f_{\theta}^{1} is
4.5 Parametric Competitive Ratio Analysis
We summarize Lemmasย 4.3 ,ย 4.7 ,ย 4.13 , ย 4.16 and ย 4.20 to get the following theorem.
Theorem 4.21
โ ๐ ๐ 8 1-2m\delta-me^{\frac{-(h+\alpha)N}{8}}-me^{\frac{-(h+\eta)N}{8}} , Algorithmย 2 has a competitive ratio of at least
4 ๐ท 2 \frac{e^{-0.25}}{4D+2} inย Naori and Raz ( 2019 ) .
Corollary 4.22
2 ๐ท 1 superscript ๐ท 2 \alpha=C_{0}N^{-\frac{1}{3}},\beta=0.935\frac{2D}{2D+1},\eta=\theta=\frac{2D}{2D+1},\gamma=0.084\frac{2D+1}{D^{2}} . Here, C 0 subscript ๐ถ 0 C_{0} is the constant such that 1 โ 3 โ ฮ = 1 โ ฮฑ 1 3 ฮ 1 ๐ผ 1-3\Delta=1-\alpha .
2 ๐ท 1 superscript ๐ท 2 \gamma=0.084\frac{2D+1}{D^{2}} .
However, for the general cases, the competitive ratio in Theoremย 4.21 is too complicated to find out the optimal or near optimal choice of parameters. Then we try to fix some parameters to tune others and give some feasible lower bounds. We denote the heavy LP phase and light LP phase as LP phases and denote the heavy max matching phase and light max packing phase as max phases. We first consider the case that there are no max phases, then consider the case that there are no LP phases to get some intuitions for the choices of the parameters.
4.5.1 No Max Phases
We first consider the special case that there are no max phases, i.e., ฮฒ = ฮท ๐ฝ ๐ \beta=\eta and ฮธ = 1 ๐ 1 \theta=1 . In the following proposition, we provide a parameter choice with a feasible lower bound of competitive ratio, the proof is in the appendix.
Proposition 4.24
Algorithmย 2 can achieve a competitive ratio with at least
4.5.2 No LP phases
In this section, we consider a set of special parameter choice: ฮฑ = ฮฒ ๐ผ ๐ฝ \alpha=\beta and ฮท = ฮธ ๐ ๐ \eta=\theta , i.e., no heavy and light LP phases. We further assume our choice of ฮฑ ๐ผ \alpha is at most 1 โ h 1 โ 1-h . In this case, the formula of competitive ratio becomes min โก { F H , F L } superscript ๐น ๐ป superscript ๐น ๐ฟ \min\{F^{H},F^{L}\} where
We update the value of f 1 subscript ๐ 1 f_{1} and f 2 subscript ๐ 2 f_{2} as below:
We observe that though we cannot find out optimal ฮท ๐ \eta and ฮฑ ๐ผ \alpha easily, we can fix the value of ฮท ๐ \eta , and find the optimal ฮฑ ๐ผ \alpha related to ฮท ๐ \eta . Firstly, we discuss the case that ฮท โค 1 โ h ๐ 1 โ \eta\leq 1-h .
Proposition 4.25
Given ฮท โค 1 โ h ๐ 1 โ \eta\leq 1-h , we have competitive ratio of at least
when we set ฮธ = ฮท ๐ ๐ \theta=\eta , ฮฒ = ฮฑ ๐ฝ ๐ผ \beta=\alpha and
โ ๐ ๐ท โ f_{1}=(1-(h+\eta))(1+2D)+2D\ln(h+\eta)+h(1+2D\ln(h+\eta)-Dh) .
In the following corollary, we give a choice of ฮท โค 1 โ h ๐ 1 โ \eta\leq 1-h and show a feasible competitive ratio.
Corollary 4.26
When h โค 1 2 โ D โ 1 2 ๐ท h\leq\frac{1}{2D} , we can achieve a competitive ratio of at least
1 โ โ \eta=\theta=\frac{2D}{2D+1}(1+h)-h .
Secondly, we consider the case that ฮท > 1 โ h ๐ 1 โ \eta>1-h and give a special choice of ฮท ๐ \eta in the following proposition and two corollaries. The details of proof are showed in appendix.
Proposition 4.27
Given ฮท > 1 โ h ๐ 1 โ \eta>1-h , we have competitive ratio of at least
๐ท subscript ๐ 2 1 superscript ๐ 1 โ ๐ โ \alpha_{1}=\exp\{1-(Df_{2}+1)e^{1-h-\eta}\}-h and ฮฑ 2 = exp โก { โ e 1 โ h โ ฮท } โ h subscript ๐ผ 2 superscript ๐ 1 โ ๐ โ \alpha_{2}=\exp\{-e^{1-h-\eta}\}-h .
Corollary 4.28
1 1 4 superscript ๐ท 2 1 1 2 ๐ท h\geq h_{0}:=(2D^{2}+1)(\sqrt{1+\frac{1}{4D^{2}}}-1)+\frac{1}{2D} , we can achieve a competitive ratio of at least
1 1 4 superscript ๐ท 2 \eta=\theta=2-\frac{1}{2D}-\sqrt{1+\frac{1}{4D^{2}}} .
Observing the choices of ฮท ๐ \eta in the corollary above, to ensure the optimal ฮท ๐ \eta which maximizes e 1 โ h โ ฮท โ f 2 superscript ๐ 1 โ ๐ subscript ๐ 2 e^{1-h-\eta}f_{2} satisfying the assumption ฮท > 1 โ h ๐ 1 โ \eta>1-h , the condition that h โฅ h 0 โ subscript โ 0 h\geq h_{0} is necessary. Thus, for the case where 1 2 โ D < h < h 0 1 2 ๐ท โ subscript โ 0 \frac{1}{2D}<h<h_{0} , we choose the smallest ฮท ๐ \eta which keeps ฮท > 1 โ h ๐ 1 โ \eta>1-h below, and provide the following corollary. The proof is omitted because it is straightforward from Propositionย 4.27 .
Corollary 4.29
1 1 4 superscript ๐ท 2 1 1 2 ๐ท \frac{1}{2D}<h<h_{0}:=(2D^{2}+1)(\sqrt{1+\frac{1}{4D^{2}}}-1)+\frac{1}{2D} , we can achieve competitive ratio
where we set ฮธ = ฮท = 1 โ 1 2 โ D ๐ ๐ 1 1 2 ๐ท \theta=\eta=1-\frac{1}{2D} , ฮฒ = ฮฑ ๐ฝ ๐ผ \beta=\alpha and
Here ฮฑ 1 = exp โก { 1 โ 5 4 โ e 1 2 โ D โ h } โ h subscript ๐ผ 1 1 5 4 superscript ๐ 1 2 ๐ท โ โ \alpha_{1}=\exp\{1-\frac{5}{4}e^{\frac{1}{2D}-h}\}-h and ฮฑ 2 = exp โก { โ e 1 2 โ D โ h } โ h subscript ๐ผ 2 superscript ๐ 1 2 ๐ท โ โ \alpha_{2}=\exp\{-e^{\frac{1}{2D}-h}\}-h .
We next compare the competitive ratios of our algorithm under three different choices of parameters: general parameters, the parameters such that only LP phases are contained (corresponding to Sectionย 4.5.1 ), and the parameters such that only max phases are contained (corresponding to Sectionย 4.5.2 ), which is shown in Figureย 2 . Here, for the parameters corresponding to only LP phases, since the analysis in Sectionย 4.5.1 contains some approximation under the assumption that N ๐ N is large which may lead to a very poor performance under the case when N ๐ N is small, we use the other parameters suggested in Propositionย 4.24 and enumerate an optimal ฮฑ ๐ผ \alpha as the parameters. For the parameters corresponding to only max phases, we directly apply the parameters advised by Corollariesย 4.26 ,ย 4.28 andย 4.29 .
1 1 4 superscript ๐ท 2 1 1 2 ๐ท h_{0}:=(2D^{2}+1)(\sqrt{1+\frac{1}{4D^{2}}}-1)+\frac{1}{2D} , corresponding to the parameters advised in Corollaryย 4.28 . This is from the assumption that ฮฑ โค 1 โ h ๐ผ 1 โ \alpha\leq 1-h in Sectionย 4.5.2 , which makes it easier for us to give an explicit choice of parameters. But such assumption may damage the performance when h โ h is large. In contrast, though the competitive ratio under only LP phases is relatively low when h โ h is small, the competitive ratio has a great increase with the increase of h โ h . Further, in most cases except the case where D = 1 ๐ท 1 D=1 and N = 2000 ๐ 2000 N=2000 , the competitive ratio under only LP phases can reach a comparable or even higher competitive ratio than that under only max phases.
According to the above analysis, we can suggest the choices of parameters based on the values of h โ h . Though the optimal choices of parameters may be hard to calculate, when h โ h is small, we can adopt the parameters provided in Sectionย 4.5.1 . When h โ h is large, we can use the parameters provided in Sectionย 4.5.2 , which allows us to reach a relatively good performance.
![online generalized assignment problem Refer to caption](https://ar5iv.labs.arxiv.org/html/2302.08234/assets/x10.png)
5 Experiments
In this section, we first apply our algorithms to a dataset from a popular task assignment platform: EverySender Tong etย al. ( 2016 ) to examine the effectiveness of our algorithms on online matching problem. Secondly, we test the performance of our algorithms on online multidimensional GAP problem over a synthetic dataset.
5.1 Online Matching
Dataset and preprocessing. EverySender dataset includes a set of workers and tasks. Each worker and task has a location ( x , y ) ๐ฅ ๐ฆ (x,y) . The data also provide the successful rate for each worker and payoff for each task. We process the data in the following way. We treat each worker as an online item and each task as an offline bin. We divide the map into a grid map where each grid has a size of ( d โ x , d โ y ) ๐ ๐ฅ ๐ ๐ฆ (dx,dy) , and group every worker/task in the same grid as one type. As a result, we generate a normalized location ( x ~ = โ x / d โ x โ , y ~ = โ y / d โ y โ ) formulae-sequence ~ ๐ฅ ๐ฅ ๐ ๐ฅ ~ ๐ฆ ๐ฆ ๐ ๐ฆ (\tilde{x}=\lfloor x/dx\rfloor,\tilde{y}=\lfloor y/dy\rfloor) for each type of worker and task. We use ( x ~ , y ~ ) ~ ๐ฅ ~ ๐ฆ (\tilde{x},\tilde{y}) to indicate the worker/taskโs type. We use the frequency of each worker type to approximate its arrival rate. We use the average successful rate (payoff) of the same type of workers as the successful rate (payoff) of this type. For each pair of worker and task, we add an edge between them if the Euclidean distance between them is smaller than a given threshold, and the weight of this edge is the product of the corresponding successful rate and payoff.
Algorithms. We test two heuristic algorithms based on Algorithmย 1 and a greedy algorithm.
Grd : The greedy algorithm. For each arrival i ๐ i of type v ๐ฃ v , match it to the available offline vertex u ๐ข u with the largest weight w u โ v subscript ๐ค ๐ข ๐ฃ w_{uv} .
Sam1 : Algorithmย 1 with ฮฑ = max โก { e e โ h โ 1 , 0 } ๐ผ superscript ๐ superscript ๐ โ 1 0 \alpha=\max\{e^{e^{-h}}-1,0\} , ฮฒ = 1 โ h ๐ฝ 1 โ \beta=1-h and ฮณ = 1 ๐พ 1 \gamma=1 .
Sam2 : Algorithmย 1 with ฮฑ = max โก { e e โ h โ 1 , 0 } ๐ผ superscript ๐ superscript ๐ โ 1 0 \alpha=\max\{e^{e^{-h}}-1,0\} , ฮฒ = 1 ๐ฝ 1 \beta=1 and ฮณ = 1 ๐พ 1 \gamma=1 .
According to Theoremย 3.10 , the optimal ฮฑ ๐ผ \alpha and ฮฒ ๐ฝ \beta depends on the values of h โ h and N ๐ N . However, N ๐ N is not known by us in practice. We then choose a universal value of ฮฑ ๐ผ \alpha and ฮฒ ๐ฝ \beta to run our algorithm. Specifically, we set ฮฑ = max โก { e e โ h โ 1 , 0 } ๐ผ superscript ๐ superscript ๐ โ 1 0 \alpha=\max\{e^{e^{-h}}-1,0\} as suggested by Zhang etย al. ( 2022 ) , since this ฮฑ ๐ผ \alpha maximizes the ratio in Theoremย 3.10 when there is no LP phase. We choose two values for ฮฒ ๐ฝ \beta : ฮฒ = 1 โ h ๐ฝ 1 โ \beta=1-h and ฮฒ = 1 ๐ฝ 1 \beta=1 . These two values are chosen because according to Theoremย 3.10 , the analyses for ฮฒ โค 1 โ h ๐ฝ 1 โ \beta\leq 1-h and ฮฒ > 1 โ h ๐ฝ 1 โ \beta>1-h are different, which implies ฮฒ = 1 โ h ๐ฝ 1 โ \beta=1-h is a critical value. ฮฒ = 1 ๐ฝ 1 \beta=1 is considered since it refers to a special case where only LP phase is used in the exploitation period.
Results and discussion. We compare the ratio of different algorithms at different h โ h and T ๐ T and summarize the results in Figureย 3 and Figureย 4 .
In Figureย 3 , we test different h โ h , fixing T = 1000 ๐ 1000 T=1000 and T = 2000 ๐ 2000 T=2000 . We can see that when h โ h becomes larger, Sam1 and Sam2 โs performance shows an increasing trend and Grd โs performance keeps almost unchanged. This is consistent with the analysis in Theoremย 3.10 that when h โ h goes larger, the performance of our algorithms becomes better. By comparing Sam1 ย and Sam2 , we find that Sam2 does not always dominate Sam1 under different parameters ( h โ h and T ๐ T ). In fact, according to Figureย 3(b) , when T ๐ T is large, Sam1 consistently outperforms Sam2 when h โ h is large. It implies that adding the maximum matching phase indeed helps improve the algorithmโs performance in many instances.
In summary, increasing the historical data size (a larger h โ h ) or increasing the planning horizon (a larger T ๐ T ) helps improve the performance of our heuristic algorithms even when N ๐ N is small. Our heuristic algorithms can outperform greedy algorithm when h โ h and T ๐ T is large.
![online generalized assignment problem Refer to caption](https://ar5iv.labs.arxiv.org/html/2302.08234/assets/x16.png)
5.2 Online Multidimensional GAP
Dataset and preprocessing. For online multidimensional GAP, we use a synthetic dataset to evaluate our algorithms. Let ๐ฐ โ [ a , b ] ๐ฐ ๐ ๐ \mathcal{U}[a,b] denote a uniform distribution on the interval [ a , b ] ๐ ๐ [a,b] . A problem instance is generated as follows. First we define U = [ m ] ๐ delimited-[] ๐ U=[m] and V = [ n ] ๐ delimited-[] ๐ V=[n] . For each u โ U ๐ข ๐ u\in U and v โ V ๐ฃ ๐ v\in V , we define an edge ( u , v ) ๐ข ๐ฃ (u,v) with weight w u โ v subscript ๐ค ๐ข ๐ฃ w_{uv} which is generated from a uniform distribution ๐ฐ โ [ 0 , 1 ] ๐ฐ 0 1 \mathcal{U}[0,1] . For each edge ( u , v ) ๐ข ๐ฃ (u,v) , the d ๐ d -th demand r u โ v d superscript subscript ๐ ๐ข ๐ฃ ๐ r_{uv}^{d} is generated from a uniform distribution ๐ฐ โ [ 0 , 1 ] ๐ฐ 0 1 \mathcal{U}[0,1] . We initialize the d ๐ d -th capacity as c โฅ 1 ๐ 1 c\geq 1 for each bin u ๐ข u . For the arrival rates, we generate a value l v subscript ๐ ๐ฃ l_{v} according to a uniform distribution ๐ฐ โ [ 0 , 1 ] ๐ฐ 0 1 \mathcal{U}[0,1] , then normalize the value as the arrival rates for each v ๐ฃ v , i.e., ฮป v = l v โ v l v subscript ๐ ๐ฃ subscript ๐ ๐ฃ subscript ๐ฃ subscript ๐ ๐ฃ \lambda_{v}=\frac{l_{v}}{\sum_{v}l_{v}} . After the normalization, the expected number of total arrivals is T ๐ T .
Algorithms. We test three heuristic algorithms based on Algorithmย 2 and a greedy algorithm.
Grd : The greedy algorithm. For each arrival i ๐ i of type v ๐ฃ v , match it to the available offline vertex u ๐ข u with the largest edge weight w u โ v subscript ๐ค ๐ข ๐ฃ w_{uv} . Here โavailableโ means u ๐ข u has enough capacity for edge ( u , v ) ๐ข ๐ฃ (u,v) .
Sam-Max : The Algorithmย 2 has sampling phase and max phases, the parameters are chosen according to Corollariesย 4.26 ,ย 4.28 andย 4.29 .
Sam-LP : The Algorithmย 2 has LP phases and sampling phase. ฮฑ = 0.05 ๐ผ 0.05 \alpha=0.05 , ฮฒ = ฮท ๐ฝ ๐ \beta=\eta where ฮท ๐ \eta is the solution of e D โ ฮท = 5 โ ฮท 4 superscript ๐ ๐ท ๐ 5 ๐ 4 e^{D\eta}=\frac{5-\eta}{4} . ฮธ = 1 ๐ 1 \theta=1 , ฮณ = ฮณ โฒ = 1 ๐พ superscript ๐พ โฒ 1 \gamma=\gamma^{\prime}=1 .
๐ 1 ๐ 2 \theta=\eta+\frac{1-\eta}{2} , ฮณ = ฮณ โฒ = 1 ๐พ superscript ๐พ โฒ 1 \gamma=\gamma^{\prime}=1 .
Now we explain why we choose these heuristic algorithms. For Sam-Max , we consider there are no LP phases (see Sectionย 4.5.2 ), and the parameters are advised by Corollariesย 4.26 ,ย 4.28 andย 4.29 . For Sam-LP , as we do not know the exact value of N ๐ N , we simply choose a small value of ฮฑ = 0.05 ๐ผ 0.05 \alpha=0.05 . ฮฒ ๐ฝ \beta , ฮท ๐ \eta , ฮณ ๐พ \gamma are chosen according to the Propositionย 4.24 . For ฮณ โฒ superscript ๐พ โฒ \gamma^{\prime} , we choose ฮณ โฒ = 1 superscript ๐พ โฒ 1 \gamma^{\prime}=1 because the value ฮณ = 1 2 โ D ๐พ 1 2 ๐ท \gamma=\frac{1}{2D} suggested by Propositionย 4.24 is too conservative. To be specific, because there is no other phase after light LP phase, we can choose a large value of ฮณ โฒ superscript ๐พ โฒ \gamma^{\prime} in practice. For Sam-Mix , the values of ฮฑ ๐ผ \alpha , ฮท ๐ \eta , ฮณ ๐พ \gamma and ฮณ โฒ superscript ๐พ โฒ \gamma^{\prime} come from Sam-LP , and we divide the heavy (or light) LP phase of Sam-LP into heavy (or light) LP phase and heavy (or light) max phase with equal size.
![online generalized assignment problem Refer to caption](https://ar5iv.labs.arxiv.org/html/2302.08234/assets/x20.png)
Results and discussion. We summarize the results in Figureย 5 and Figureย 6 . Each error bar shows the average empirical competitive ratio ยฑ standard error plus-or-minus average empirical competitive ratio standard error \text{average empirical competitive ratio}\pm\text{standard error} .
Besides the analysis of ratios, we can also see the trends of standard errors. When D = 1 ๐ท 1 D=1 , the standard errors of Sam-Mix and Sam-LP are similar with the error of Grd , while the ratios of our algorithms are much larger than Grd ( T > 50 ๐ 50 T>50 ) which means our algorithms are robust when D = 1 ๐ท 1 D=1 . When D = 2 ๐ท 2 D=2 , the standard errors of Sam-Mix and Sam-LP become larger. This is because the โvarianceโ between each randomized graph becomes larger, then the variance of ratio becomes larger.
To summarize, Sam-Mix has the best performance among all tested algorithms and Sam-LP can achieve similar performance as Sam-Mix when h > 0.5 โ 0.5 h>0.5 and T > 250 ๐ 250 T>250 . When h โ h and T ๐ T is increasing, the performance of Sam-Mix and Sam-LP becomes better. The marginal utility of h โ h and T ๐ T is decreasing when h โ h and T ๐ T are large. The performance becomes stable when h โ h and T ๐ T are larger than some thresholds, i.e., if we already have โenough dataโ (large historical data h โ h and planning horizon T ๐ T ), we do not need more data. In practice, the thresholds of h โ h and T ๐ T are small comparing with the theoretical analysis. We can use Sam-Mix for all non-trivial cases ( h > 0 โ 0 h>0 and T > 50 ๐ 50 T>50 ), and if we have larger h โ h and T ๐ T , we can also use Sam-LP which only needs to use LP phases.
6 Conclusions
We study the online multidimensional GAP problem in this paper. We initiate our study from a special case that corresponds to an online bipartite matching. We provide a sample-based multi-phase algorithm and present its performance guarantee in terms of the historical data size and the minimal number of arrivals for each online item type. We then generalize the algorithm to the general online multidimensional GAP and also provide a parametric performance guarantee. From the parametric form of the competitive ratio, we analyze the effect of historical data size, the Poisson arrival model, and the dimension of capacity (demand) on the algorithmโs performance. Finally, we test our algorithms for online matching and online multidimensional GAP problem.
- Aggarwal etย al. (2011) Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , 1253โ1264 (SIAM).
- Alaei etย al. (2013) Alaei S, Hajiaghayi M, Liaghat V (2013) The online stochastic generalized assignment problem. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 11โ25 (Springer).
- Albers etย al. (2020) Albers S, Khan A, Ladewig L (2020) Improved Online Algorithms for Knapsack and GAP in the Random Order Model. arXiv:2012.00497 [cs] URL http://arxiv.org/abs/2012.00497 , arXiv: 2012.00497.
- Azar etย al. (2014) Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , 1358โ1377 (SIAM).
- Canonne (2019) Canonne C (2019) A short note on poisson tail bounds URL http://www.cs.columbia.edu/~ccanonne/files/misc/2017-poissonconcentration.pdf .
- Correa etย al. (2019) Correa J, Dรผtting P, Fischer F, Schewior K (2019) Prophet inequalities for iid random variables from an unknown distribution. Proceedings of the 2019 ACM Conference on Economics and Computation , 3โ17.
- Feldman etย al. (2009) Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 2009 50th Annual IEEE Symposium on Foundations of Computer Science , 117โ126 (IEEE).
- Feng etย al. (2023) Feng Y, Qiu G, Wu X, Zhou S (2023) Improved competitive ratio for edge-weighted online stochastic matching. arXiv preprint arXiv:2302.05633 .
- Gamarnik and Squillante (2005) Gamarnik D, Squillante MS (2005) Analysis of stochastic online bin packing processes. Stochastic models 21(2-3):401โ425.
- Huang and Shu (2021) Huang Z, Shu X (2021) Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program. arXiv:2103.13024 [cs] URL http://arxiv.org/abs/2103.13024 , arXiv: 2103.13024.
- Huang etย al. (2022) Huang Z, Shu X, Yan S (2022) The Power of Multiple Choices in Online Stochastic Matching. arXiv:2203.02883 [cs] URL http://arxiv.org/abs/2203.02883 , arXiv: 2203.02883.
- Jaillet and Lu (2014) Jaillet P, Lu X (2014) Online Stochastic Matching: New Algorithms with Better Bounds. Mathematics of Operations Research 39(3):624โ646, ISSN 0364-765X, 1526-5471, URL http://dx.doi.org/10.1287/moor.2013.0621 .
- Jiang etย al. (2021) Jiang J, Ma W, Zhang J (2021) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. ArXiv abs/2107.02058.
- Kaplan etย al. (2021) Kaplan H, Naori D, Raz D (2021) Online Weighted Matching with a Sample. arXiv:2104.05771 [cs] URL http://arxiv.org/abs/2104.05771 , arXiv: 2104.05771.
- Karp etย al. (1990) Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proceedings of the twenty-second annual ACM symposium on Theory of computing , 352โ358.
- Kesselheim etย al. (2013) Kesselheim T, Radke K, Tรถnnis A, Vรถcking B (2013) An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. Hutchison D, Kanade T, Kittler J, Kleinberg JM, Mattern F, Mitchell JC, Naor M, Nierstrasz O, Panduย Rangan C, Steffen B, Sudan M, Terzopoulos D, Tygar D, Vardi MY, Weikum G, Bodlaender HL, Italiano GF, eds., Algorithms โ ESA 2013 , volume 8125, 589โ600 (Berlin, Heidelberg: Springer Berlin Heidelberg), ISBN 978-3-642-40449-8 978-3-642-40450-4, URL http://dx.doi.org/10.1007/978-3-642-40450-4_50 , series Title: Lecture Notes in Computer Science.
- Liu etย al. (2023) Liu H, Zhang H, Luo K, Xu Y, Xu Y, Tong W (2023) Online generalized assignment problem with historical information. Computers & Operations Research 149:106047.
- Manshadi etย al. (2012) Manshadi VH, Gharan SO, Saberi A (2012) Online Stochastic Matching: Online Actions Based on Offline Statistics. Mathematics of Operations Research 37(4):559โ573, ISSN 0364-765X, URL https://www.jstor.org/stable/23358636 , publisher: INFORMS.
- Mehta (2013) Mehta A (2013) Online Matching and Ad Allocation. Foundations and Trends in Theoretical Computer Science 8 (4):265โ368, URL http://dx.doi.org/10.1561/0400000057 .
- Naori and Raz (2019) Naori D, Raz D (2019) Online Multidimensional Packing Problems in the Random-Order Model 15 pages, URL http://dx.doi.org/10.4230/LIPICS.ISAAC.2019.10 , artwork Size: 15 pages Medium: application/pdf Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany Version Number: 1.0.
- Tong etย al. (2016) Tong Y, She J, Ding B, Wang L, Chen L (2016) Online mobile micro-task allocation in spatial crowdsourcing. 2016 IEEE 32Nd international conference on data engineering (ICDE) , 49โ60 (IEEE).
- Wainwright (2019) Wainwright MJ (2019) High-dimensional statistics: A non-asymptotic viewpoint , volumeย 48 (Cambridge university press).
- Yan (2022) Yan S (2022) Edge-weighted online stochastic matching: Beating 1-1/e. ArXiv abs/2210.12543.
- Zhang etย al. (2022) Zhang H, Du R, Luo K, Tong W (2022) Learn from history for online bipartite matching. Journal of Combinatorial Optimization 44(5):3611โ3640.
Omitted Proofs See 2.1
The number of arrivals n ๐ n follows a Poisson distribution with parameter N ๐ N . According to Fact 4 from Canonne ( 2019 ) , we can directly prove this lemma.
According to the property of Poisson arrival process, the differences between consecutive two t i subscript ๐ก ๐ t_{i} s follow an exponential distribution. Chapter 2 of Wainwright ( 2019 ) gives us the concentration bounds of an exponential distribution random variable.
1 ฮ \frac{1-\alpha}{1+\Delta} and the optimal value of L โ P โ ( ๐ , T ) ๐ฟ ๐ ๐ ๐ LP(\bm{\lambda},T) .
1 ฮ subscript ๐ฅ ๐ข ๐ฃ \{\frac{1-\alpha}{1+\Delta}x_{uv}\} is a feasible solution of L โ P โ ( ๐ ^ , T โฒ ) ๐ฟ ๐ ^ ๐ superscript ๐ โฒ LP(\hat{\bm{\lambda}},T^{\prime}) .
1 ฮ 1 0\leq\frac{1-\alpha}{1+\Delta}\leq 1 , we can directly induce the feasibility of these two constraints in L โ P โ ( ๐ ^ , T โฒ ) ๐ฟ ๐ ^ ๐ superscript ๐ โฒ LP(\hat{\bm{\lambda}},T^{\prime}) .
The matching event between u ๐ข u and one type v โ V ๐ฃ ๐ v\in V before time t ๐ก t follows a Poisson distribution with a parameter ฮป v โ ฮณ โ x ^ u โ v ฮป ^ v โ T โฒ โ ( t โ ฮฑ โ T ) subscript ๐ ๐ฃ ๐พ subscript ^ ๐ฅ ๐ข ๐ฃ subscript ^ ๐ ๐ฃ superscript ๐ โฒ ๐ก ๐ผ ๐ \lambda_{v}\frac{\gamma\hat{x}_{uv}}{\hat{\lambda}_{v}T^{\prime}}(t-\alpha T) , where the first term corresponds to the arrival rate, the second term corresponds to the matching probability and the third term corresponds to the time horizon.
From the independency of different online types in V ๐ V , we have:
1 ฮ subscript ^ ๐ ๐ฃ \lambda_{v}\leq(1+\Delta)\cdot\hat{\lambda}_{v} and the second inequality is from Constraintย ( 2 b ).
1 ฮ ๐ก ๐ผ ๐ 1 ๐ผ ๐ ๐พ subscript ^ ๐ฅ ๐ข ๐ฃ subscript ^ ๐ ๐ฃ superscript ๐ โฒ subscript ๐ ๐ฃ differential-d ๐ก w_{uv}\int_{\alpha T}^{\beta T}e^{-\gamma(1+\Delta)\frac{t-\alpha T}{(1-\alpha)T}}\cdot\gamma\frac{\hat{x}_{uv}}{\hat{\lambda}_{v}T^{\prime}}\cdot\lambda_{v}dt , where inside the integration, the first term corresponds to the unmatched event before t ๐ก t , the second corresponds to the matching probability and the third is the arrival rate. The such term can be lower bound by
1 ฮ 1 2 ฮ \frac{1-\Delta}{1+\Delta}>1-2\Delta .
1 ฮ ๐ฝ ๐ผ 1 ๐ผ OPT \frac{1-2\Delta}{1+\Delta}(1-\alpha)(1-e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}})\operatorname{{\textrm{OPT}}}\geq(1-3\Delta)(1-\alpha)(1-e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}})\operatorname{{\textrm{OPT}}} .
subscript ๐ฅ superscript subscript ๐ ๐ฅ 2 ๐ ๐ฅ subscript : ๐ฅ ๐ฆ ๐ฅ ๐ฆ subscript ๐ ๐ฅ subscript ๐ ๐ฆ ๐ ๐ฅ ๐ฅ ๐ฆ subscript ๐ฅ subscript ๐ ๐ฅ ๐ ๐ฅ \sum_{x}p_{x}^{2}f(x)+\sum_{(x,y):x\neq y}p_{x}p_{y}\frac{f(x)}{x}y\geq\sum_{x}p_{x}f(x) . By moving the first term in LHS to the right and 1 โ p x = โ y โ x p y 1 subscript ๐ ๐ฅ subscript ๐ฆ ๐ฅ subscript ๐ ๐ฆ 1-p_{x}=\sum_{y\neq x}p_{y} , we get โ ( x , y ) : x โ y p x โ p y โ f โ ( x ) x โ y โฅ โ x p x โ ( โ y โ x p y ) โ f โ ( x ) subscript : ๐ฅ ๐ฆ ๐ฅ ๐ฆ subscript ๐ ๐ฅ subscript ๐ ๐ฆ ๐ ๐ฅ ๐ฅ ๐ฆ subscript ๐ฅ subscript ๐ ๐ฅ subscript ๐ฆ ๐ฅ subscript ๐ ๐ฆ ๐ ๐ฅ \sum_{(x,y):x\neq y}p_{x}p_{y}\frac{f(x)}{x}y\geq\sum_{x}p_{x}(\sum_{y\neq x}p_{y})f(x) . If we place the two terms considering the same pairs of x ๐ฅ x and y ๐ฆ y together, we get:
๐ ๐ฅ ๐ฅ ๐ฅ ๐ ๐ฆ ๐ฆ ๐ฆ \frac{f(x)}{x}y+\frac{f(y)}{y}x\geq\frac{f(x)}{x}x+\frac{f(y)}{y}y .
We denote the size of V โฒ superscript ๐ โฒ V^{\prime} excluding the type v ๐ฃ v for the present item i ๐ i as k โฒ superscript ๐ โฒ k^{\prime} . If the total number of arrivals in the time interval [ โ h โ T , ฮฒ โ T ) โ ๐ ๐ฝ ๐ [-hT,\beta T) is w ๐ค w , we have:
โ ๐ ๐ก \textrm{Pr}[E|k^{\prime}]\geq e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}}\frac{{\mathbb{E}}[w|k^{\prime}]}{k^{\prime}}=e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}}\frac{(h+\beta)T}{hT+t} , where the last equation is because the value of ๐ผ โ [ w | k โฒ ] k โฒ ๐ผ delimited-[] conditional ๐ค superscript ๐ โฒ superscript ๐ โฒ \frac{{\mathbb{E}}[w|k^{\prime}]}{k^{\prime}} is exactly equal to the ratio between the length of the time horizon according to the symmetry of time. We next take expectations over all k โฒ superscript ๐ โฒ k^{\prime} and finish the proof.
superscript ๐ โฒ 1 {\mathbb{E}}[\frac{1}{k^{\prime}+1}] , we can treat the distribution of k โฒ superscript ๐ โฒ k^{\prime} as a Poisson distribution with some fixed parameter ฮป โฒ superscript ๐ โฒ \lambda^{\prime} because of the additive property of independent Poisson distribution. We have:
superscript ๐ โฒ 1 ๐ก 1 โ ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ {\mathbb{E}}[\frac{num}{k^{\prime}+1}]={\mathbb{E}}[num]{\mathbb{E}}[\frac{1}{k^{\prime}+1}]\leq\frac{(t-(1-h)T)\sum_{v\in V}\lambda_{v}}{T\sum_{v\in V}\lambda_{v}} , which is equal to the wanted term.
superscript ๐ โฒ 1 ๐ก ๐ฝ ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ {\mathbb{E}}[\frac{num}{k^{\prime}+1}]={\mathbb{E}}[num]{\mathbb{E}}[\frac{1}{k^{\prime}+1}]\leq\frac{(t-\beta T)\sum_{v\in V}\lambda_{v}}{T\sum_{v\in V}\lambda_{v}} , which is equal to the wanted term.
By applying Lemmaย 3.5 , the expected reward during the maximum matching phase is at least โซ ฮฒ โ T T โ v โ V ฮป v โ OPT T โ โ v โ V ฮป v โ Pr โ [ E ] โ d โ t superscript subscript ๐ฝ ๐ ๐ subscript ๐ฃ ๐ โ subscript ๐ ๐ฃ OPT ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ Pr delimited-[] ๐ธ ๐ ๐ก \int_{\beta T}^{T}\sum_{v\in V}\lambda_{v}\cdot\frac{\operatorname{{\textrm{OPT}}}}{T\sum_{v\in V}\lambda_{v}}\cdot\text{Pr}[E]dt , where E ๐ธ E is the event that the corresponding offline vertex u ๐ข u of the online vertex i ๐ i arriving at time t ๐ก t is unmatched before time t ๐ก t . The next we need to integrate the term Pr โ [ E ] Pr delimited-[] ๐ธ \text{Pr}[E] to get the answer. We then can utilize Lemmaย 3.6 and Lemmaย 3.7 for ฮฒ โค 1 โ h ๐ฝ 1 โ \beta\leq 1-h and Lemmaย 3.8 for ฮฒ > 1 โ h ๐ฝ 1 โ \beta>1-h to get the required values.
1 ฮ \frac{1-\alpha}{1+\Delta} and the optimal value of L โ P H โ ( ๐ , T ) ๐ฟ superscript ๐ ๐ป ๐ ๐ LP^{H}(\bm{\lambda},T) .
We utilize the techniques used in the proof of Lemmaย 3.3 and prove the arguments. The packing event of an item of type v โ V ๐ฃ ๐ v\in V into bin u ๐ข u before time t ๐ก t follows a Poisson distribution with a parameter ฮป v โ ฮณ โ x ^ u โ v ฮป ^ v โ T โฒ โ ( t โ ฮฑ โ T ) subscript ๐ ๐ฃ ๐พ subscript ^ ๐ฅ ๐ข ๐ฃ subscript ^ ๐ ๐ฃ superscript ๐ โฒ ๐ก ๐ผ ๐ \lambda_{v}\frac{\gamma\hat{x}_{uv}}{\hat{\lambda}_{v}T^{\prime}}(t-\alpha T) , where the first term corresponds to the arrival rate, the second term corresponds to the matching probability and the third term corresponds to the time horizon. This is from the property of the compound Poisson process where each random variable is a Bernoulli distribution. From the independency of different online types in V ๐ V , we have:
1 ฮ subscript ^ ๐ ๐ฃ \lambda_{v}\leq(1+\Delta)\cdot\hat{\lambda}_{v} and the second inequality is from Constraintย ( 3 b ).
1 ฮ ๐ก ๐ผ ๐ 1 ๐ผ ๐ ๐ท ๐พ subscript ^ ๐ฅ ๐ข ๐ฃ subscript ^ ๐ ๐ฃ superscript ๐ โฒ subscript ๐ ๐ฃ differential-d ๐ก w_{uv}\int_{\alpha T}^{\beta T}e^{-\gamma(1+\Delta)\frac{t-\alpha T}{(1-\alpha)T}D}\cdot\gamma\frac{\hat{x}_{uv}}{\hat{\lambda}_{v}T^{\prime}}\cdot\lambda_{v}dt , where inside the integration, the first term corresponds to the unmatched event before t ๐ก t , the second corresponds to the matching probability and the third is the arrival rate. The such term can be lower bound by
1 ฮ ๐ฝ ๐ผ 1 ๐ผ ๐ท superscript OPT ๐ป \frac{1}{D}\frac{1-2\Delta}{1+\Delta}(1-\alpha)(1-e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}D})\operatorname{{\textrm{OPT}}}^{H}\geq\frac{1}{D}(1-3\Delta)(1-\alpha)(1-e^{-\gamma(1+\Delta)\frac{\beta-\alpha}{1-\alpha}D})\operatorname{{\textrm{OPT}}}^{H} .
We adopt the ideas behind Lemmaย 3.6 here. We denote the size of V โฒ superscript ๐ โฒ V^{\prime} excluding the type v ๐ฃ v for the present item i ๐ i as k โฒ superscript ๐ โฒ k^{\prime} . If the total number of arrivals in the time interval [ โ h โ T , ฮฒ โ T ) โ ๐ ๐ฝ ๐ [-hT,\beta T) is w ๐ค w , we have:
โ ๐ ๐ก \textrm{Pr}[E|k^{\prime}]\geq{q_{\alpha}^{\beta}}\frac{{\mathbb{E}}[w|k^{\prime}]}{k^{\prime}}={q_{\alpha}^{\beta}}\frac{(h+\beta)T}{hT+t} , where the last equation is because the value of ๐ผ โ [ w | k โฒ ] k โฒ ๐ผ delimited-[] conditional ๐ค superscript ๐ โฒ superscript ๐ โฒ \frac{{\mathbb{E}}[w|k^{\prime}]}{k^{\prime}} is exactly equal to the ratio between the length of the time horizon according to the symmetry of time. We next take expectations over all k โฒ superscript ๐ โฒ k^{\prime} and finish the proof.
superscript ๐ โฒ 1 {\mathbb{E}}[\frac{num}{k^{\prime}+1}] by ๐ผ โ [ n โ u โ m ] โ 1 ๐ผ โ [ k โฒ ] ๐ผ delimited-[] ๐ ๐ข ๐ 1 ๐ผ delimited-[] superscript ๐ โฒ {\mathbb{E}}[num]\frac{1}{{\mathbb{E}}[k^{\prime}]} , which is equal to the wanted term.
By applying Lemmaย 4.8 , the expected reward during the maximum matching phase is at least โซ ฮฒ โ T T โ v โ V ฮป v โ OPT H D โ T โ โ v โ V ฮป v โ Pr โ [ E ] โ d โ t superscript subscript ๐ฝ ๐ ๐ subscript ๐ฃ ๐ โ subscript ๐ ๐ฃ superscript OPT ๐ป โ ๐ท ๐ subscript ๐ฃ ๐ subscript ๐ ๐ฃ Pr delimited-[] ๐ธ ๐ ๐ก \int_{\beta T}^{T}\sum_{v\in V}\lambda_{v}\cdot\frac{\operatorname{{\textrm{OPT}}}^{H}}{D\cdot T\sum_{v\in V}\lambda_{v}}\cdot\text{Pr}[E]dt , where E ๐ธ E is the event that the corresponding offline vertex u ๐ข u of the online item i ๐ i arriving at time t ๐ก t is unmatched before time t ๐ก t . The next we need to integrate the term Pr โ [ E ] Pr delimited-[] ๐ธ \text{Pr}[E] to get the answer. We then can utilize Lemmaย 4.9 for ฮท โค 1 โ h ๐ 1 โ \eta\leq 1-h , Lemmasย 4.9 and ย 4.10 for ฮฒ โค 1 โ h < ฮท ๐ฝ 1 โ ๐ \beta\leq 1-h<\eta and Lemmaย 4.11 for ฮฒ > 1 โ h ๐ฝ 1 โ \beta>1-h to get the required values.
1 superscript ฮ โฒ 1 \frac{1-\eta}{1+\Delta^{\prime}}\leq 1 , by Constraintsย ( 4 b ) for L โ P 0 L โ ( ๐ , T , C ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ๐ ๐ ๐ถ LP_{0}^{L}(\bm{\lambda},T,C) , these constraints hold under our given solution. We now can compare the optimal values. Assuming a set U โฒ superscript ๐ โฒ U^{\prime} which contains only the bin without heavy items, the expectation of the optimal value of L โ P 0 L โ ( ๐ ^ , T โฒ , C ยฏ ) ๐ฟ superscript subscript ๐ 0 ๐ฟ ^ ๐ superscript ๐ โฒ ยฏ ๐ถ LP_{0}^{L}(\hat{\bm{\lambda}},T^{\prime},\bar{C}) is equal to
Here, โ โ [ U โฒ ] โ delimited-[] superscript ๐ โฒ \mathbb{P}[U^{\prime}] represents the probability for one U โฒ superscript ๐ โฒ U^{\prime} . The inequality is from the definition of q ฮฑ ฮฒ โ q ฮฒ ฮท superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ {q_{\alpha}^{\beta}}q_{\beta}^{\eta} and Lemmaย 4.2 .
Let Z u โ t d superscript subscript ๐ ๐ข ๐ก ๐ Z_{ut}^{d} denote the consumed capacity of u ๐ข u โs d ๐ d dimension by time t ๐ก t .
1 superscript ฮ โฒ 1 ๐ ๐ superscript subscript ๐ถ ๐ข ๐ {\mathbb{E}}[Z_{ut}^{d}]=\sum_{v\in V}\lambda_{v}(t-\eta T)r_{uv}^{d}\gamma^{\prime}\cdot\frac{\hat{y}_{uv}}{\hat{\lambda}_{v}T^{\prime}}\leq(t-\eta T)\frac{\gamma^{\prime}(1+\Delta^{\prime})}{(1-\eta)T}\sum_{v}\hat{y}_{uv}r_{uv}^{d}\leq(t-\eta T)\frac{\gamma^{\prime}(1+\Delta^{\prime})}{(1-\eta)T}C_{u}^{d} .
1 superscript ฮ โฒ ๐ ๐ 1 ๐ \sum_{v\in V,u\in U^{\prime},(v,u)\in{\mathcal{E}}^{L}}w_{uv}\hat{y}_{uv}\cdot(1-\Delta^{\prime})\gamma^{\prime}\frac{\theta-\eta}{1-\eta}(1-D\gamma^{\prime}(1+\Delta^{\prime})\frac{\theta-\eta}{1-\eta}) . By applying Lemmaย 4.14 , we finish our proof.
Before we start our proof, we first need to show the following claim holds. Claim. If we denote the total number of arrivals during a time horizon and the expected value of L โ P 1 L ๐ฟ superscript subscript ๐ 1 ๐ฟ LP_{1}^{L} given the total number of arrivals is x ๐ฅ x and f โ ( x ) ๐ ๐ฅ f(x) , respectively, then f โ ( x ) x ๐ ๐ฅ ๐ฅ \frac{f(x)}{x} is a decreasing function. Such property holds because of the following reasons. Since the number of arrivals are fixed, the Poisson arrival model can be seen as following independent and identical distributions, where the probability of each type v ๐ฃ v is proportional to the arrival rate ฮป v subscript ๐ ๐ฃ \lambda_{v} . Under this model, since all arrivals are identical in expectations, it suffices to show removing the last arrival can still satisfy the constraints of L โ P 1 L ๐ฟ superscript subscript ๐ 1 ๐ฟ LP_{1}^{L} . For an optimal solution { y u โ v } subscript ๐ฆ ๐ข ๐ฃ \{y_{uv}\} of L โ P 1 L โ ( V โฒ ) ๐ฟ superscript subscript ๐ 1 ๐ฟ superscript ๐ โฒ LP_{1}^{L}(V^{\prime}) , we can show { y u โ v : v โ v โฒ } conditional-set subscript ๐ฆ ๐ข ๐ฃ ๐ฃ superscript ๐ฃ โฒ \{y_{uv}:v\neq v^{\prime}\} is a feasible solution of L โ P 1 L โ ( V โฒ โ { v โฒ } ) ๐ฟ superscript subscript ๐ 1 ๐ฟ superscript ๐ โฒ superscript ๐ฃ โฒ LP_{1}^{L}(V^{\prime}-\{v^{\prime}\}) , where v โฒ superscript ๐ฃ โฒ v^{\prime} is the last arrival. This obviously holds for Constraintsย ( 5 a ) andย ( 5 c ). For Constraintsย 5 b , only the left hand side can be decreased, so they still hold. We now finish the proof of the claim. For the lemma, we adopt the ideas behind the proof of Lemmaย 3.5 and prove our statements. We denote the size of the set V โฒ superscript ๐ โฒ V^{\prime} (Stepย 33 ) by k ๐ k and the optimal value of LPย ( 5 ) by OPT โฒ superscript OPT โฒ \operatorname{{\textrm{OPT}}}^{\prime} . Since each vertex in V โฒ superscript ๐ โฒ V^{\prime} arrives in the system in the same way, by symmetry, if we fix the size | V โฒ | superscript ๐ โฒ |V^{\prime}| of the set V โฒ superscript ๐ โฒ V^{\prime} as k โฒ superscript ๐ โฒ k^{\prime} , we have ๐ผ [ w โ | | V โฒ | = k โฒ ] = ๐ผ [ OPT โฒ | | V โฒ | = k โฒ ] k โฒ {\mathbb{E}}[w_{\ell}|~{}|V^{\prime}|=k^{\prime}]=\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{\prime}|~{}|V^{\prime}|=k^{\prime}]}{k^{\prime}} . We then assume the time horizon in V โฒ superscript ๐ โฒ V^{\prime} is T โฒ superscript ๐ โฒ T^{\prime} . If T โฒ < T superscript ๐ โฒ ๐ T^{\prime}<T corresponding to the case t < ( 1 โ h ) โ T ๐ก 1 โ ๐ t<(1-h)T in Stepย 33 , we denote the set of the arriving vertices in the following time horizon of T โ T โฒ ๐ superscript ๐ โฒ T-T^{\prime} by V โฒโฒ superscript ๐ โฒโฒ V^{\prime\prime} . For each realization of V โฒโฒ superscript ๐ โฒโฒ V^{\prime\prime} , if OPT โฒโฒ superscript OPT โฒโฒ \operatorname{{\textrm{OPT}}}^{\prime\prime} is the optimal value of L โ P 1 L โ ( V โฒ โช V โฒโฒ ) ๐ฟ superscript subscript ๐ 1 ๐ฟ superscript ๐ โฒ superscript ๐ โฒโฒ LP_{1}^{L}(V^{\prime}\cup V^{\prime\prime}) , ๐ผ [ OPT โฒ | | V โฒ | = k โฒ ] k โฒ โฅ ๐ผ [ OPT โฒโฒ | | V โฒ | = k โฒ , V โฒโฒ ] k โฒ + | V โฒโฒ | \frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{\prime}|~{}|V^{\prime}|=k^{\prime}]}{k^{\prime}}\geq\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{\prime\prime}|~{}|V^{\prime}|=k^{\prime},V^{\prime\prime}]}{k^{\prime}+|V^{\prime\prime}|} , from the claim above. We then assume the size of V โฒโฒ superscript ๐ โฒโฒ V^{\prime\prime} is k โฒโฒ superscript ๐ โฒโฒ k^{\prime\prime} and take expectations over all V โฒโฒ superscript ๐ โฒโฒ V^{\prime\prime} with the same size, we have ๐ผ [ OPT โฒ | | V โฒ | = k โฒ ] k โฒ โฅ ๐ผ [ OPT โฒโฒ | | V โฒ | = k โฒ , | V โฒโฒ | = k โฒโฒ ] k โฒ + k โฒโฒ \frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{\prime}|~{}|V^{\prime}|=k^{\prime}]}{k^{\prime}}\geq\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{\prime\prime}|~{}|V^{\prime}|=k^{\prime},|V^{\prime\prime}|=k^{\prime\prime}]}{k^{\prime}+k^{\prime\prime}} . If we take the expectations over all possible k โฒ superscript ๐ โฒ k^{\prime} and k โฒโฒ superscript ๐ โฒโฒ k^{\prime\prime} , we denote the set of arriving vertices in the time interval [ 0 , T ] 0 ๐ [0,T] as V ๐ V , and we have ๐ผ โ [ w โ ] โฅ ๐ผ โ [ ๐ผ [ OPT L | | V | = k ] k ] {\mathbb{E}}[w_{\ell}]\geq{\mathbb{E}}[\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{L}|~{}|V|=k]}{k}] , where the outside expectation in the right-hand side if taken over k ๐ k . This is because OPT L superscript OPT ๐ฟ \operatorname{{\textrm{OPT}}}^{L} corresponds to the optimal value of L โ P 1 L ๐ฟ superscript subscript ๐ 1 ๐ฟ LP_{1}^{L} in a time horizon of exactly T ๐ T . For the second case where T โฒ = T superscript ๐ โฒ ๐ T^{\prime}=T corresponding to t โฅ ( 1 โ h ) โ T ๐ก 1 โ ๐ t\geq(1-h)T in Stepย 33 , we can directly get ๐ผ [ w โ | | V โฒ | = k โฒ ] = ๐ผ [ OPT โฒ | | V โฒ | = k โฒ ] k โฒ = ๐ผ [ OPT L | | V | = k ] k {\mathbb{E}}[w_{\ell}|~{}|V^{\prime}|=k^{\prime}]=\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{\prime}|~{}|V^{\prime}|=k^{\prime}]}{k^{\prime}}=\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{L}|~{}|V|=k]}{k} , because both V ๐ V and V โฒ superscript ๐ โฒ V^{\prime} is from a time horizon of T ๐ T and sampled in the same way. We can also get ๐ผ โ [ w โ ] โฅ ๐ผ โ [ ๐ผ [ OPT L | | V | = k ] k ] {\mathbb{E}}[w_{\ell}]\geq{\mathbb{E}}[\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{L}|~{}|V|=k]}{k}] by expectation over k ๐ k . If suffices to show ๐ผ โ [ ๐ผ [ OPT L | | V | = k ] k ] โฅ OPT L T โ โ v โ V ฮป v {\mathbb{E}}[\frac{{\mathbb{E}}[\operatorname{{\textrm{OPT}}}^{L}|~{}|V|=k]}{k}]\geq\frac{\operatorname{{\textrm{OPT}}}^{L}}{T\sum_{v\in V}\lambda_{v}} . If we treat k ๐ k as the independent variable x ๐ฅ x and use the above function f โ ( x ) ๐ ๐ฅ f(x) , following the same procedure in Lemmaย 3.5 , we finish our proof.
๐ก ๐ ๐ ๐ superscript subscript ๐ ๐ ๐ {\mathbb{E}}_{k,num}[1-\frac{2D\cdot num}{k+1}-2Dq_{\eta}^{\theta}]\geq 1-2D(\frac{t-\theta T}{T}+q_{\eta}^{\theta}) .
The expected reward during the light phase can be calculated by โซ ฮธ โ T T โ v โ V ฮป v โ OPT L T โ โ v ฮป v โ q ฮฑ ฮฒ โ q ฮฒ ฮท โ Pr โ [ E ] โ d โ t superscript subscript ๐ ๐ ๐ subscript ๐ฃ ๐ โ subscript ๐ ๐ฃ superscript OPT ๐ฟ ๐ subscript ๐ฃ subscript ๐ ๐ฃ superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ Pr delimited-[] ๐ธ ๐ ๐ก \int_{\theta T}^{T}\sum_{v\in V}\lambda_{v}\cdot\frac{\operatorname{{\textrm{OPT}}}^{L}}{T\sum_{v}\lambda_{v}}\cdot{q_{\alpha}^{\beta}}q_{\beta}^{\eta}\text{Pr}[E]dt . Here, the term โ v โ V ฮป v subscript ๐ฃ ๐ subscript ๐ ๐ฃ \sum_{v\in V}\lambda_{v} represents the arrival rate for any online type, the term OPT L T โ โ v ฮป v superscript OPT ๐ฟ ๐ subscript ๐ฃ subscript ๐ ๐ฃ \frac{\operatorname{{\textrm{OPT}}}^{L}}{T\sum_{v}\lambda_{v}} is the bound of the weight of one matching edge from Lemmaย 4.17 , and the last term q ฮฑ ฮฒ โ q ฮฒ ฮท โ Pr โ [ E ] superscript subscript ๐ ๐ผ ๐ฝ superscript subscript ๐ ๐ฝ ๐ Pr delimited-[] ๐ธ {q_{\alpha}^{\beta}}q_{\beta}^{\eta}\text{Pr}[E] represents the probability that the chosen edge can be matched successfully. Pr โ [ E ] Pr delimited-[] ๐ธ \text{Pr}[E] is the probability mentioned in Lemmaย 4.19 , which should be further categorized for the following calculation. By calculus, we can get the corresponding value.
We consider the parameter settings that ฮฒ = ฮท ๐ฝ ๐ \beta=\eta and ฮธ = 1 ๐ 1 \theta=1 , i.e., there is no heavy maximum matching phase or light maximum packing phase. We choose ฮฑ = C 0 โ N โ 1 3 โช 1 ๐ผ subscript ๐ถ 0 superscript ๐ 1 3 much-less-than 1 \alpha=C_{0}N^{-\frac{1}{3}}\ll 1 where C 0 subscript ๐ถ 0 C_{0} is a constant that ฮฑ ๐ผ \alpha satisfies 3 โ 8 โ l โ n โ 1 ฮด ฮฑ โ N = ฮฑ 3 8 ๐ ๐ 1 ๐ฟ ๐ผ ๐ ๐ผ 3\sqrt{\frac{8ln\frac{1}{\delta}}{\alpha N}}=\alpha . Now we rewrite the ratio min โก { F H , F L } superscript ๐น ๐ป superscript ๐น ๐ฟ \min\{F^{H},F^{L}\} in Theoremย 4.21 where
ฮ ๐ผ ๐ผ ๐ e^{-\gamma(1+\Delta)\frac{\eta-\alpha}{1-\alpha}D}\approx e^{-D\gamma(1+\Delta)(\eta-\alpha)(1+\alpha)}\approx e^{-D\gamma(\eta+\eta(\Delta+\alpha)-\alpha)}\approx e^{-\gamma\eta D}\cdot e^{-\gamma\eta D(\Delta+\alpha-\frac{\alpha}{\eta})}\approx e^{-\gamma\eta D}(1-\gamma\eta D(\Delta+\alpha-\frac{\alpha}{\eta})) . These approximations are according to the infinitesimal ฮ ฮ \Delta and ฮฑ ๐ผ \alpha , and e โ x โ 1 โ x superscript ๐ ๐ฅ 1 ๐ฅ e^{-x}\approx 1-x when x ๐ฅ x is small. Thus,
Similar for F L superscript ๐น ๐ฟ F^{L} , we can have the same order of the infinitesimal. Adopting ฮ โฒ โค ฮ superscript ฮ โฒ ฮ \Delta^{\prime}\leq\Delta , we can have a constant C 2 subscript ๐ถ 2 C_{2} such that
To find optimal choice of parameters, we ignore the infinitesimal term first. Then our problem is
Since ฮณ โฒ superscript ๐พ โฒ \gamma^{\prime} only influences F L superscript ๐น ๐ฟ F^{L} , we can choose ฮณ โฒ = 1 2 โ D superscript ๐พ โฒ 1 2 ๐ท \gamma^{\prime}=\frac{1}{2D} to maximize F L superscript ๐น ๐ฟ F^{L} . Then we can update the competitive ratio as
Observing that F H = 1 D โ ( 1 โ e โ ฮณ โ D โ ฮท ) superscript ๐น ๐ป 1 ๐ท 1 superscript ๐ ๐พ ๐ท ๐ F^{H}=\frac{1}{D}(1-e^{-\gamma D\eta}) and F L = 1 4 โ D โ e โ ฮณ โ D โ ฮท โ ( 1 โ ฮท ) superscript ๐น ๐ฟ 1 4 ๐ท superscript ๐ ๐พ ๐ท ๐ 1 ๐ F^{L}=\frac{1}{4D}e^{-\gamma D\eta}(1-\eta) are increasing with respect to ฮณ ๐พ \gamma , we choose ฮณ = 1 ๐พ 1 \gamma=1 . Then for the choice of ฮท ๐ \eta , since F H superscript ๐น ๐ป F^{H} increases with ฮท ๐ \eta while F L superscript ๐น ๐ฟ F^{L} decreases with ฮท ๐ \eta , we choose the ฮท ๐ \eta that satisfies 1 D โ ( 1 โ e โ D โ ฮท ) = 1 4 โ D โ e โ D โ ฮท โ ( 1 โ ฮท ) 1 ๐ท 1 superscript ๐ ๐ท ๐ 1 4 ๐ท superscript ๐ ๐ท ๐ 1 ๐ \frac{1}{D}(1-e^{-D\eta})=\frac{1}{4D}e^{-D\eta}(1-\eta) . That is, ฮท = ฮท 1 ๐ subscript ๐ 1 \eta=\eta_{1} satisfies:
It is easy to check that there only exists one ฮท 1 subscript ๐ 1 \eta_{1} and this ฮท 1 subscript ๐ 1 \eta_{1} is feasible. Then the ratio is
Then add back the infinity small part and choose C 3 = max โก { C 1 , C 2 } subscript ๐ถ 3 subscript ๐ถ 1 subscript ๐ถ 2 C_{3}=\max\{C_{1},C_{2}\} , we have the ratio
We first assume that F H โฅ F L superscript ๐น ๐ป superscript ๐น ๐ฟ F^{H}\geq F^{L} , according to ฮท โค 1 โ h ๐ 1 โ \eta\leq 1-h , we have
โ ๐ superscript ๐ 1 โ \alpha\leq\alpha_{2}=(h+\eta)e^{-1}-h , the ratio is increasing while the ratio is decreasing when ฮฑ โฅ ฮฑ 2 ๐ผ subscript ๐ผ 2 \alpha\geq\alpha_{2} . If ฮฑ 2 โฅ max โก { 0 , ฮฑ 1 } subscript ๐ผ 2 0 subscript ๐ผ 1 \alpha_{2}\geq\max\{0,\alpha_{1}\} , the optimal ฮฑ = ฮฑ 2 ๐ผ subscript ๐ผ 2 \alpha=\alpha_{2} . If ฮฑ 2 < max โก { 0 , ฮฑ 1 } subscript ๐ผ 2 0 subscript ๐ผ 1 \alpha_{2}<\max\{0,\alpha_{1}\} , then F H superscript ๐น ๐ป F^{H} is decreasing when ฮฑ โฅ max โก { 0 , ฮฑ 1 } ๐ผ 0 subscript ๐ผ 1 \alpha\geq\max\{0,\alpha_{1}\} , so we choose optimal ฮฑ = max โก { 0 , ฮฑ 1 } ๐ผ 0 subscript ๐ผ 1 \alpha=\max\{0,\alpha_{1}\} . Then to summarize, the optimal ฮฑ ๐ผ \alpha is
and the ratio is
โ ๐ ๐ท โ f_{1}=(1-(h+\eta))(1+2D)+2D\ln(h+\eta)+h(1+2D\ln(h+\eta)-Dh) . By calculus, we can find out that
When h โค 1 2 โ D โ 1 2 ๐ท h\leq\frac{1}{2D} , we can verify that such ฮท ๐ \eta is no greater than 1 โ h 1 โ 1-h . Now we have
โ ๐ ๐ท subscript ๐ 1 โ 0 h+\eta-Df_{1}-h\geq 0 . Then given the value of ฮท ๐ \eta and f 1 subscript ๐ 1 f_{1} , we denote
Now we only need to show that g โ ( h ) โฅ 0 ๐ โ 0 g(h)\geq 0 for 0 โค h โค 1 2 โ D 0 โ 1 2 ๐ท 0\leq h\leq\frac{1}{2D} . First check the first order derivative g โฒ โ ( h ) superscript ๐ โฒ โ g^{\prime}(h) of g โ ( h ) ๐ โ g(h) :
Then check the second order derivative
2 ๐ท 1 0 g^{\prime}(h)\leq g^{\prime}\left(\frac{1}{2D}\right)=-\frac{1}{2D+1}\leq 0 which means
โ ๐ ๐ท subscript ๐ 1 0 h+\eta-Df_{1}\geq 0 already satisfies. Then the choice of ฮฑ ๐ผ \alpha is
And the competitive ratio is
โ ๐ผ superscript ๐ 1 โ ๐ subscript ๐ 2 F^{L}=(h+\alpha)e^{1-h-\eta}\cdot f_{2} and f 2 = ( 1 โ ฮท ) โ ( 1 โ D โ ( 1 โ ฮท ) ) subscript ๐ 2 1 ๐ 1 ๐ท 1 ๐ f_{2}=(1-\eta)(1-D(1-\eta)) . We first assume that F H โฅ F L superscript ๐น ๐ป superscript ๐น ๐ฟ F^{H}\geq F^{L} , according to ฮท > 1 โ h ๐ 1 โ \eta>1-h we have
โ ๐ผ 1 superscript ๐ 1 โ ๐ F^{H}=\frac{1}{D}(h+\alpha)(\ln\frac{1}{h+\alpha}+1-e^{1-h-\eta}) , we can see that when ฮฑ โค ฮฑ 2 := exp โก { โ e 1 โ h โ ฮท } โ h ๐ผ subscript ๐ผ 2 assign superscript ๐ 1 โ ๐ โ \alpha\leq\alpha_{2}:=\exp\{-e^{1-h-\eta}\}-h , F H superscript ๐น ๐ป F^{H} is increasing, and when ฮฑ โฅ ฮฑ 2 ๐ผ subscript ๐ผ 2 \alpha\geq\alpha_{2} , F H superscript ๐น ๐ป F^{H} is decreasing. We can also have ฮฑ 2 โค 1 โ h subscript ๐ผ 2 1 โ \alpha_{2}\leq 1-h . Then, we have the following cases:
ฮฑ 2 โฅ max โก { ฮฑ 1 , 0 } subscript ๐ผ 2 subscript ๐ผ 1 0 \alpha_{2}\geq\max\{\alpha_{1},0\} : set ฮฑ = ฮฑ 2 = max โก { ฮฑ 1 , ฮฑ 2 , 0 } ๐ผ subscript ๐ผ 2 subscript ๐ผ 1 subscript ๐ผ 2 0 \alpha=\alpha_{2}=\max\{\alpha_{1},\alpha_{2},0\} ;
ฮฑ 2 โค max โก { ฮฑ 1 , 0 } subscript ๐ผ 2 subscript ๐ผ 1 0 \alpha_{2}\leq\max\{\alpha_{1},0\} : set ฮฑ = max โก { ฮฑ 1 , 0 } = max โก { ฮฑ 1 , ฮฑ 2 , 0 } ๐ผ subscript ๐ผ 1 0 subscript ๐ผ 1 subscript ๐ผ 2 0 \alpha=\max\{\alpha_{1},0\}=\max\{\alpha_{1},\alpha_{2},0\} .
Then to summarize, the optimal ฮฑ ๐ผ \alpha is
and ratio is
According to Propositionย 4.27 , consider the case that ฮฑ 1 โฅ 1 โ h subscript ๐ผ 1 1 โ \alpha_{1}\geq 1-h , the optimal ฮฑ = 1 โ h ๐ผ 1 โ \alpha=1-h , and competitive ratio is e 1 โ h โ ฮท โ f 2 superscript ๐ 1 โ ๐ subscript ๐ 2 e^{1-h-\eta}f_{2} . This value is maximized when we choose
Then we have
It is easy to check that ฮท โฅ 1 โ h ๐ 1 โ \eta\geq 1-h because
And ฮท โค 1 ๐ 1 \eta\leq 1 because
4 superscript ๐ท 2 1 2 ๐ท h+\eta\geq 1+D(\sqrt{4D^{2}+1}-2D) . Then we need to prove that
The statement holds because of our assumption. We can also see that h 0 โค 1 subscript โ 0 1 h_{0}\leq 1 because
1 1 2 ๐ \sqrt{1+a}\leq 1+\frac{1}{2}a for a โฅ 0 ๐ 0 a\geq 0 and last inequality is obvious because D ๐ท D is a positive integer. Then according to the Propositionย 4.27 , the competitive ratio is e 1 โ h โ ฮท โ ( 1 โ ฮท ) โ ( 1 โ D โ ( 1 โ ฮท ) ) superscript ๐ 1 โ ๐ 1 ๐ 1 ๐ท 1 ๐ e^{1-h-\eta}(1-\eta)(1-D(1-\eta)) .
![online generalized assignment problem ar5iv homepage](https://ar5iv.labs.arxiv.org/assets/ar5iv.png)
- DOI: 10.1007/978-3-642-40328-6_2
- Corpus ID: 6309972
The Online Stochastic Generalized Assignment Problem
- S. Alaei , M. Hajiaghayi , Vahid Liaghat
- Published in International Workshop andโฆ 21 August 2013
- Computer Science, Mathematics
55 Citations
Sample-based online generalized assignment problem with unknown poisson arrivals.
- Highly Influenced
Improved Online Algorithms for Knapsack and GAP in the Random Order Model
Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack, online algorithms for the santa claus problem, online adaptive bin packing with overflow, stochastic k-server: how should uber work, new algorithms, better bounds, and a novel model for online stochastic matching, size-stochastic knapsack online contention resolution schemes, online sampling and decision making with low entropy, stochastic matching : new algorithms and bounds โ, 21 references, near optimal online algorithms and fast approximation algorithms for resource allocation problems, tight approximation algorithms for maximum general assignment problems, approximating the stochastic knapsack problem: the benefit of adaptivity.
- Highly Influential
Improved approximation results for stochastic knapsack problems
A ( 2 + )-approximation algorithm for the stochastic knapsack problem, online prophet-inequality matching with applications to ad allocation, a ptas for the multiple knapsack problem, online ad assignment with free disposal, approximation algorithms for allocation problems: improving the factor of 1 - 1/e, automated online mechanism design and prophet inequalities, related papers.
Showing 1 through 3 of 0 Related Papers
Solving Generalized Assignment Problem using Branch-And-Price
Oct 27, 2021
Table of Contents
Generalized assignment problem, dantzig-wolfe decomposition, column generation, standalone model, initial solution, branching rule, branch-and-price.
One of the best known and widely researched problems in combinatorial optimization is Knapsack Problem:
- given a set of items, each with its weight and value,
- select a set of items maximizing total value
- that can fit into a knapsack while respecting its weight limit.
The most common variant of a problem, called 0-1 Knapsack Problem can be formulated as follows:
- \(m\) - number of items;
- \(x_i\) - binary variable indicating whether item is selected;
- \(v_i\) - value of each items;
- \(w_i\) - weight of each items;
- \(W\) - maximum weight capacity.
As often happens in mathematics, or science in general, an obvious question to ask is how the problem can be generalized. One of generalization is Generalized Assignment Problem. It answers question - how to find a maximum profit assignment of \(m\) tasks to \(n\) machines such that each task (\(i=0, \ldots, m\)) is assigned to exactly one machine (\(j=1, \ldots, n\)), and one machine can have multiple tasks assigned to subject to its capacity limitation. Its standard formulation is presented below:
- \(n\) - number of machines;
- \(m\) - number of tasks;
- \(x_{ij}\) - binary variable indicating whether task \(i\) is assigned to machine \(j\);
- \(v_{ij}\) - value/profit of assigning task \(i\) to machine \(j\);
- \(w_{ij}\) - weight of assigning task \(i\) to machine \(j\);
- \(c_j\) - capacity of machine \(j\).
Branch-and-price
Branch-and-price is generalization of branch-and-bound method to solve integer programs (IPs),mixed integer programs (MIPs) or binary problems. Both branch-and-price, branch-and-bound, and also branch-and-cut, solve LP relaxation of a given IP. The goal of branch-and-price is to tighten LP relaxation by generating a subset of profitable columns associated with variables to join the current basis.
Branch-and-price builds at the top of branch-and-bound framework. It applies column generation priori to branching. Assuming maximization problem, branching occurs when:
- Column Generation is finished (i.e. no profitable columns can be found).
- Objective value of the current solution is greater than best lower bound.
- The current solution does not satisfy integrality constraints.
However, if only first two conditions are met but not the third one, meaning the current solution satisfies integrality constraints, then the best solution and lower bound are updated (lower bound is tightened) with respectively the current solution and its objective value.
The crucial element needed to apply branch-and-price successfully is to find branching scheme. It is tailored to specific problem to make sure that it does not destroy problem structure and can be used in pricing subproblem to effectively generate columns that enter Restricted Master Problem (RMP) while respecting branching rules .
Below is flow diagram describing branch-and-price method:
![online generalized assignment problem Branch-and-Price flow diagram](https://grzegorz-siekaniec.github.io/bits-of-this-bits-of-that/assets/images/2021/OCT/branch-and-price-flow-chart.png)
The successful application B&P depends on tight/strong model formulation. Model formulation is considered tight if solution of its LP relaxation satisfies (frequently) integrality constraints. One of structured approaches to come up with such a formulation is to use Dantzig-Wolfe Decomposition technique. We will see example of it applied to Generalized Assignment Problem (GAP).
A standard formulation was described above. Now, letโs try to reformulate problem. Let
be a set containing all feasible solutions to Knapsack problem for \(j\)-th machine. Clearly, \(S_j\) contains finite number of points, so \(S_j = \{ \mathbf{z}_j^1, \ldots, \mathbf{z}_j^{K_j} \}\), where \(\mathbf{z}_j^k \in \{0, 1\}^{m}\). You can think about \(\mathbf{z}_j^k \in \{0, 1\}^{m}\) as 0-1 encoding of tasks that form \(k\)-th feasible solution for machine \(j\). Now, let \(S = \{ \mathbf{z}_1^1, \ldots, \mathbf{z}_1^{K_1}, \ldots, \mathbf{z}_n^1, \ldots, \mathbf{z}_n^{K_n} \}\) be a set of all feasible solution to GAP. It, potentially, contains a very large number of elements. Then, every point \(x_{ij}\) can be expressed by the following convex combination:
where \(z_{ij}^k \in \{0, 1\}\), and \(z_{ij}^k = 1\) iff task \(i\) is assigned to machine \(j\) in \(k\)-th feasible solution for the machine.
Now, letโs use this representation to reformulate GAP:
Note that we do not need capacity restrictions as they are embedded into definition of feasible solution for machine \(j\).
Now that we have formulation that is suitable for column generation, letโs turn our attention to it.
Column generation is another crucial component of branch-and-price. There are many great resources devoted to column generation so I will mention only core points:
- Column generation is useful when a problemโs pool of feasible solutions contains many elements but only small subset will be present in the optimal solution.
- There exists subproblem (called often pricing problem) that can be used to effectively generate columns that should enter RMP.
- Column generation starts with initial feasible solution.
- Pricing subproblem objective function is updated with dual of the current solution.
- Columns with positive reduced cost, in case of maximization problem, enter problem.
- Procedure continues until such columns exist.
Below is flow diagram describing column generation method:
![online generalized assignment problem Column generation flow diagram](https://grzegorz-siekaniec.github.io/bits-of-this-bits-of-that/assets/images/2021/OCT/column-generation-flow-diagram.png)
Implementation
Letโs see how one can approach implementation of B&P to solve Generalized Assignment Problem. Below is discussion about main concepts and few code excerpts, a repository containing all code can be found on github .
An example of problem instance taken from [1] is:
It is always good idea to have a reference simple(r) implementation that can be used to validate our results using more sophisticated methods. In our case it is based on standard problem formulation. Implementation can be found in repo by checking classes GAPStandaloneModelBuilder and GAPStandaloneModel . Formulation for a problem instance presented above looks as follows:
Now letโs try to examine building blocks of B&P to discus main part at the end, once all the puzzles are there.
To start column generation process, we need to have an initial solution. One possible way to derive it is to use two-phase Simplex method. In first step, you add slack variables to each constraint and set objective function as their sum. Then you minimize the problem. If your solution has objective value \(0\), then first of all you have initial solution and you know that your problem is feasible. In case you end up with positive value for any of slack variables, you can conclude that the problem is infeasible. You can stop here.
I took a different approach and came up with simple heuristic that generate initial solution. I have not analyzed it thoroughly so I am not sure if it is guaranteed to always return feasible solution if one exists. Its idea is quite simple:
- Construct bipartite graph defined as \(G=(V, A)\), where \(V = T \cup M\) โ \(T\) is set of tasks and obviously \(M\) is set of machines. There exists arc \(a = (t, m)\) if \(w_{tm} \le rc_{m}\), where \(rc_{m}\) is remaining capacity for machine \(m\). Initially remaining capacity is equal to capacity of machine and with each iteration, and assignment of task to machine it is being update. If \(\vert A \vert = 0\), then stop.
- Solve a minimum weight matching problem.
- Update assignments โ say that according to solution task \(t_0\) should be assigned to machine \(m_0\), then \(\overline{rc}_{m_0} = rc_{m_0} - w_{t_0 m_0}\).
- Find a machine where task is contributing with the lowest weight โ say machine \(m_0 = \arg\min \{ m: w_{t_0 m} \}\).
- Free up remaining capacity so there is enough space for \(t_0\) on machine \(m_0\). Any tasks that were de-assigned in a process are added to pool of unassigned tasks.
- Repeat until there are no unassigned tasks.
See details on github .
As we said before the most important piece needed to implement B&P is branching rules which does not destroy structure of subproblem. Letโs consider non-integral solution to RMP. Given convexity constraint it means that there exists machine \(j_0\) and at least two, and for sake of example say exactly two, \(0 < \lambda_{j_0} ^{k_1} < 1\) and \(0 < \lambda_{j_0} ^{k_2} < 1\) such that \(\lambda_{j_0} ^{k_1} + \lambda_{j_0} ^{k_2} = 1\). Since with each of \(\lambda\)s is connected different assignment (set of tasks), then it leads us to a conclusion that there exists task \(i_0\) such that \(x_{i_0 j_0} < 1\) expressed in variables from the original formulation. Now, letโs use this information to formulate branching rule:
- left child node: a task \(i_0\) must be assigned to a machine \(j_0\).
- right child node: a task \(i_0\) cannot be assigned to a machine \(j_0\).
We can say that branching is based on \(x_{ij}\) from standard formulation. And it can be represented by:
Note that we can use the branching rule to easily to filter out initial columns for each node that do not satisfy those conditions:
- \(j = j_0\) and task \(i_0 \in T_{j_0}\), or
- \(j \neq j_0\) and task \(i_0 \notin T_{j}\).
- \(j = j_0\) and task \(i_0 \in T_{j_0}\).
See on github .
Based on the same principle, subproblemโs pool of feasible solution are created - i.e. on left child node:
- knapsack subproblem for machine \(j_0\) โ variable representing task \(i_0\) is forced to be \(1\).
- knapsack subproblem for machine \(j \neq j_0\) โ variable representing task \(i_0\) is forced to be \(0\).
Similarly for right childe node. See on github .
Below is an outline of main loop of column generation. It is an implementation of flow diagram from above so I will not spend too much time describing it. The only part maybe worth commenting is stop_due_to_no_progress - it evaluates whether column generation did not make any progress in last \(k\)-iterations and it should be stop.
Now, letโs see how constructing subproblems, solving them and then adding back column(s) to RMP looks like. We have as many subproblems as machines. Once a solution is available, we check whether it has positive reduced cost. A solution to knapsack problem corresponds to column in RMP. So if the column with positive reduced cost was identified and added, then new iteration of column generation will be executed. Gurobi allows to query information about all other identified solutions, so we can utilize this feature and add all columns that have the same objective value as optimal solution, potentially adding more than one column and hoping it will positively impact solution time.
Note that each subproblem is independent so in principle they could be solved in parallel. However due to Python Global Interpreter Lock (GIL) that prevent CPU-bounded threads to run in parallel, they are solved sequentially. Additionally depending on your Gurobi license, you might not be allowed to solve all those models in parallel even if Python would allow it.
Below you can find example of one of the RMPs:
and subproblem with dual information passed:
Now that we have all building blocks prepared, then letโs turn our attention back to B&P.
In the blog post, Branch-and-Price technique for solving MIP was explained. An example of applying B&P for Generalized Assignment Problem was presented. The solution approach used Python as programming language and Gurobi as solver.
[1] Der-San Chen, Robert G. Batson, Yu Dang (2010), Applied Integer Programming - Modeling and Solution, Willey. [2] Lasdon, Leon S. (2002), Optimization Theory for Large Systems, Mineola, New York: Dover Publications. [3] Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, Pamela H. Vance, (1998) Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329.
![online generalized assignment problem HungarianAlgorithm.com](https://hungarianalgorithm.com/pics/logo.png)
Index Assignment problem Hungarian algorithm Solve online
Solve an assignment problem online
Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.
Fill in the cost matrix ( random cost matrix ):
Don't show the steps of the Hungarian algorithm Maximize the total cost
HungarianAlgorithm.com © 2013-2024
Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals
![online generalized assignment problem online generalized assignment problem](https://deepai.org/static/images/new_heart.png)
We study an edge-weighted online stochastic Generalized Assignment Problem with unknown Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline bin is associated with a D-dimensional capacity vector and each online item is with a D-dimensional demand vector. Online arrivals are sampled from a set of online item types which follow independent but not necessarily identical Poisson processes. The arrival rate for each Poisson process is unknown. Each online item will either be packed into an offline bin which will deduct the allocated bin's capacity vector and generate a reward, or be rejected. The decision should be made immediately and irrevocably upon its arrival. Our goal is to maximize the total reward of the allocation without violating the capacity constraints. We provide a sample-based multi-phase algorithm by utilizing both pre-existing offline data (named historical data) and sequentially revealed online data. We establish its performance guarantee measured by a competitive ratio. In a simplified setting where D=1 and all capacities and demands are equal to 1, we prove that the ratio depends on the number of historical data size and the minimum number of arrivals for each online item type during the planning horizon, from which we analyze the effect of the historical data size and the Poisson arrival model on the algorithm's performance. We further generalize the algorithm to the general multidimensional and multi-demand setting, and present its parametric performance guarantee. The effect of the capacity's (demand's) dimension on the algorithm's performance is further analyzed based on the established parametric form. Finally, we demonstrate the effectiveness of our algorithms numerically.
![online generalized assignment problem online generalized assignment problem](https://deepai.org/static/images/profile-placeholder-small.png)
Zhenzhen Yan
![online generalized assignment problem online generalized assignment problem](https://images.deepai.org/publication-preview/sample-based-online-generalized-assignment-problem-with-unknown-poisson-arrivals-page-1-thumb.jpg)
Related Research
Online stochastic matching, poisson arrivals, and the natural linear program, online demand scheduling with failovers, improved online algorithms for knapsack and gap in the random order model, online learning and matching for resource allocation problems, greedy bipartite matching in random type poisson arrival model, size-stochastic knapsack online contention resolution schemes, mnl-prophet: sequential assortment selection under uncertainty.
Please sign up or login with your details
Generation Overview
AI Generator calls
AI Video Generator calls
AI Chat messages
Genius Mode messages
Genius Mode images
AD-free experience
Private images
- Includes 500 AI Image generations, 1750 AI Chat Messages, 30 AI Video generations, 60 Genius Mode Messages and 60 Genius Mode Images per month. If you go over any of these limits, you will be charged an extra $5 for that group.
- For example: if you go over 500 AI images, but stay within the limits for AI Chat and Genius Mode, you'll be charged $5 per additional 500 AI Image generations.
- Includes 100 AI Image generations and 300 AI Chat Messages. If you go over any of these limits, you will have to pay as you go.
- For example: if you go over 100 AI images, but stay within the limits for AI Chat, you'll have to reload on credits to generate more images. Choose from $5 - $1000. You'll only pay for what you use.
Out of credits
Refill your membership to continue using DeepAI
Share your generations with friends
Generalized Assignment Problem
- Reference work entry
- pp 1153โ1162
- Cite this reference work entry
- O. Erhun Kundakcioglu 3 &
- Saed Alizamir 3 ย
2883 Accesses
15 Citations
Article Outline
Introduction
โโMultiple-Resource Generalized Assignment Problem
โโMultilevel Generalized Assignment Problem
โโDynamic Generalized Assignment Problem
โโBottleneck Generalized Assignment Problem
โโGeneralized Assignment Problem with Special Ordered Set
โโStochastic Generalized Assignment Problem
โโBi-Objective Generalized Assignment Problem
โโGeneralized Multi-Assignment Problem
โโExact Algorithms
โโHeuristics
Conclusions
This is a preview of subscription content, log in via an institution to check access.
![](http://writinghelp.online/777/templates/cheerup/res/banner1.gif)
Access this chapter
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Durable hardcover edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Similar content being viewed by others
![online generalized assignment problem online generalized assignment problem](https://media.springernature.com/w215h120/springer-static/image/art%3Aplaceholder%2Fimages/placeholder-figure-springernature.png)
Some results on an assignment problem variant
Combinatorial clustering: literature review, methods, examples.
Introduction to Optimisation
Albareda-Sambola M, vanย derย Vlerk MH, Fernandez E (2006) Exact solutions to aย class of stochastic generalized assignment problems. Eur J Oper Res 173:465โ487
Article ย MATH ย Google Scholar ย
Amini MM, Racer M (1994) Aย rigorous computational comparison of alternative solution methods for the generalized assignment problem. Manag Sci 40(7):868โ890
Amini MM, Racer M (1995) Aย hybrid heuristic for the generalized assignment problem. Eur J Oper Res 87(2):343โ348
Asahiro Y, Ishibashi M, Yamashita M (2003) Independent and cooperative parallel search methods for the generalized assignment problem. Optim Method Softw 18:129โ141
Article ย MathSciNet ย MATH ย Google Scholar ย
Balachandran V (1976) An integer generalized transportation model for optimal job assignment in computer networks. Oper Res 24(4):742โ759
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316โ329
Beasley JE (1993) Lagrangean heuristics for location problems. Eur J Oper Res 65:383โ399
Cario MC, Clifford JJ, Hill RR, Yang J, Yang K, Reilly CH (2002) An investigation of the relationship between problem characteristics and algorithm performance: aย case study of the gap. IIE Trans 34:297โ313
Google Scholar ย
Cattrysse DG, Salomon M, Van LN Wassenhove (1994) Aย set partitioning heuristic for the generalized assignment problem. Eur J Oper Res 72:167โ174
Cattrysse DG, Van LN Wassenhove (1992) Aย survey of algorithms for the generalized assignment problem. Eur J Oper Res 60:260โ272
Ceselli A, Righini G (2006) Aย branch-and-price algorithm for the multilevel generalized assignment problem. Oper Res 54:1172โ1184
Chalmet L, Gelders L (1976) Lagrangean relaxation for aย generalized assignment type problem. In: Advances in OR. EURO, North Holland, Amsterdam, ppย 103โ109
Chu EC, Beasley JE (1997) Aย genetic algorithm for the generalized assignment problem. Comput Oper Res 24:17โ23
Cohen R, Katzir L, Raz D (2006) An efficient approximation for the generalized assignment problem. Inf Process Lett 100:162โ166
deย Farias Jr, Johnson EL, Nemhauser GL (2000) Aย generalized assignment problem with special ordered sets: aย polyhedral approach. Math Program, Ser A 89:187โ203
deย Farias Jr, Nemhauser GL (2001) Aย family of inequalities for the generalized assignment polytope. Oper Res Lett 29:49โ55
DeMaio A, Roveda C (1971) An all zero-one algorithm for a class of transportation problems. Oper Res 19:1406โ1418
Diaz JA, Fernandez E (2001) Aย tabu search heuristic for the generalized assignment problem. Eur J Oper Res 132:22โ38
Drexl A (1991) Scheduling of project networks by job assignment. Manag Sci 37:1590โ1602
Dyer M, Frieze A (1992) Probabilistic analysis of the generalised assignment problem. Math Program 55:169โ181
Article ย MathSciNet ย Google Scholar ย
Feltl H, Raidl GR (2004) An improved hybrid genetic algorithm for the generalized assignment problem. In: SAC '04; Proceedings of the 2004 ACM symposium on Applied computing. ACM Press, New York, ppย 990โ995
Chapter ย Google Scholar ย
Fisher ML, Jaikumar R (1981) Aย generalized assignment heuristic for vehicle routing. Netw 11:109โ124
Fisher ML, Jaikumar R, vanย Wassenhove LN (1986) Aย multiplier adjustment method for the generalized assignment problem. Manag Sci 32:1095โ1103
Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2006) Tight approximation algorithms for maximum general assignment problems. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. ACM Press, New York, ppย 611โ620
Book ย Google Scholar ย
Freling R, Romeijn HE, Morales DR, Wagelmans APM (2003) Aย branch-and-price algorithm for the multiperiod single-sourcing problem. Oper Res 51(6):922โ939
French AP, Wilson JM (2002) Heuristic solution methods for the multilevel generalized assignment problem. Jย Heuristics 8:143โ153
French AP, Wilson JM (2007) An lp-based heuristic procedure for the generalized assignment problem with special ordered sets. Comput Oper Res 34:2359โ2369
Garey MR, Johnson DS (1990) Computers and Intractability; Aย Guide to the Theory of NP-Completeness. Freeman, New York
Gavish B, Pirkul H (1991) Algorithms for the multi-resource generalized assignment problem. Manag Sci 37:695โ713
Geoffrion AM, Graves GW (1974) Multicommodity distribution system design by benders decomposition. Manag Sci 20(5):822โ844
Glover F, Hultz J, Klingman D (1979) Improved computer based planning techniques, part ii. Interfaces 4:17โ24
Gottlieb ES, Rao MR (1990) \( (1,k) \) -configuration facets for the generalized assignment problem. Math Program 46(1):53โ60
Gottlieb ES, Rao MR (1990) The generalized assignment problem: Valid inequalities and facets. Math Stat 46:31โ52
MathSciNet ย MATH ย Google Scholar ย
Guignard M, Rosenwein MB (1989) An improved dual based algorithm for the generalized assignment problem. Oper Res 37(4):658โ663
Haddadi S (1999) Lagrangian decomposition based heuristic for the generalized assignment problem. Inf Syst Oper Res 37:392โ402
Haddadi S, Ouzia H (2004) Effective algorithm and heuristic for the generalized assignment problem. Eur J Oper Res 153:184โ190
Hajri-Gabouj S (2003) Aย fuzzy genetic multiobjective optimization algorithm for aย multilevel generalized assignment problem. IEEE Trans Syst 33:214โ224
Janak SL, Taylor MS, Floudas CA, Burka M, Mountziaris TJ (2006) Novel and effective integer optimization approach for the nsf panel-assignment problem: aย multiresource and preference-constrained generalized assignment problem. Ind Eng Chem Res 45:258โ265
Article ย Google Scholar ย
Jรถrnsten K, Nasberg M (1986) Aย new lagrangian relaxation approach to the generalized assignment problem. Eur J Oper Res 27:313โ323
Jรถrnsten KO, Varbrand P (1990) Relaxation techniques and valid inequalities applied to the generalized assignment problem. Asia-P J Oper Res 7(2):172โ189
Klastorin TD (1979) An effective subgradient algorithm for the generalized assignment problem. Comp Oper Res 6:155โ164
Klastorin TD (1979) On the maximal covering location problem and the generalized assignment problem. Manag Sci 25(1):107โ112
Kogan K, Khmelnitsky E, Ibaraki T (2005) Dynamic generalized assignment problems with stochastic demands and multiple agent task relationships. Jย Glob Optim 31:17โ43
Kogan K, Shtub A, Levit VE (1997) Dgapย โ the dynamic generalized assignment problem. Ann Oper Res 69:227โ239
Kuhn H (1995) Aย heuristic algorithm for the loading problem in flexible manufacturing systems. Int J Flex Manuf Syst 7:229โ254
Laguna M, Kelly JP, Gonzfilez-Velarde JL, Glover F (1995) Tabu search for the multilevel generalized assignment problem. Eur J Oper Res 82:176โ189
Lawler E (1976) Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, Winston, New York
MATH ย Google Scholar ย
Lin BMT, Huang YS, Yu HK (2001) On the variable-depth-search heuristic for the linear-cost generalized assignment problem. Int J Comput Math 77:535โ544
Lorena LAN, Narciso MG (1996) Relaxation heuristics for aย generalized assignment problem. Eur J Oper Res 91:600โ610
Lorena LAN, Narciso MG, Beasley JE (2003) Aย constructive genetic algorithm for the generalized assignment problem. Jย Evol Optim
Lourenรงo HR, Serra D (1998) Adaptive approach heuristics for the generalized assignment problem. Technical Report 288, Department of Economics and Business, Universitat Pompeu Fabra, Barcelona
Lourenรงo HR, Serra D (2002) Adaptive search heuristics for the generalized assignment problem. Mathw Soft Comput 9(2โ3):209โ234
Martello S, Toth P (1981) An algorithm for the generalized assignment problem. In: Brans JP (ed) Operational Research '81, 9th IFORS Conference, North-Holland, Amsterdam, ppย 589โ603
Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York
Martello S, Toth P (1992) Generalized assignment problems. Lect Notes Comput Sci 650:351โ369
MathSciNet ย Google Scholar ย
Martello S, Toth P (1995) The bottleneck generalized assignment problem. Eur J Oper Res 83:621โ638
Mazzola JB, Neebe AW (1988) Bottleneck generalized assignment problems. Eng Costs Prod Econ 14(1):61โ65
Mazzola JB, Wilcox SP (2001) Heuristics for the multi-resource generalized assignment problem. Nav Res Logist 48(6):468โ483
Monfared MAS, Etemadi M (2006) The impact of energy function structure on solving generalized assignment problem using hopfield neural network. Eur J Oper Res 168:645โ654
Morales DR, Romeijn HE (2005) Handbook of Combinatorial Optimization, supplement volย B. In: Du D-Z, Pardalos PM (eds) The Generalized Assignment Problem and extensions. Springer, New York, ppย 259โ311
Narciso MG, Lorena LAN (1999) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 114:165โ177
Nauss RM (2003) Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J Comput 15(3):249โ266
Nauss RM (2005) The elastic generalized assignment problem. Jย Oper Res Soc 55:1333โ1341
Nowakovski J, Schwarzler W, Triesch E (1999) Using the generalized assignment problem in scheduling the rosat space telescope. Eur J Oper Res 112:531โ541
Nutov Z, Beniaminy I, Yuster R (2006) Aย \( (1-1/e) \) โapproximation algorithm for the generalized assignment problem. Oper Res Lett 34:283โ288
Park JS, Lim BH, Lee Y (1998) Aย lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem. Manag Sci 44(12S):271โ275
Pigatti A, deย Aragao MP, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. In: Electronic Notes in Discrete Mathematics, volย 19 of 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics, ppย 385โ395,
Osman IH (1995) Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches. OR-Spektrum 17:211โ225
Racer M, Amini MM (1994) Aย robust heuristic for the generalized assignment problem. Ann Oper Res 50(1):487โ503
Romeijn HE, Morales DR (2000) Aย class of greedy algorithms for the generalized assignment problem. Discret Appl Math 103:209โ235
Romeijn HE, Morales DR (2001) Generating experimental data for the generalized assignment problem. Oper Res 49(6):866โ878
Romeijn HE, Piersma N (2000) Aย probabilistic feasibility and value analysis of the generalized assignment problem. Jย Comb Optim 4:325โ355
Ronen D (1992) Allocation of trips to trucks operating from aย single terminal. Comput Oper Res 19(5):445โ451
Ross GT, Soland RM (1975) Aย branch and bound algorithm for the generalized assignment problem. Math Program 8:91โ103
Ross GT, Soland RM (1977) Modeling facility location problems as generalized assignment problems. Manag Sci 24:345โ357
Ross GT, Zoltners AA (1979) Weighted assignment models and their application. Manag Sci 25(7):683โ696
Savelsbergh M (1997) Aย branch-and-price algorithm for the generalized assignment problem. Oper Res 45:831โ841
Shmoys DB, Tardos E (1993) An approximation algorithm for the generalized assignment problem. Math Program 62:461โ474
Shtub A (1989) Modelling group technology cell formation as aย generalized assignment problem. Int J Prod Res 27:775โ782
Srinivasan V, Thompson GL (1973) An algorithm for assigning uses to sources in aย special class of transportation problems. Oper Res 21(1):284โ295
Stรผtzle T, Hoos H (1999) The Max-Min Ant System and Local Search for Combinatorial Optimization Problems. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics; Advances and trends in local search paradigms for optimization. Kluwer, Boston, ppย 313โ329
Toktas B, Yen JW, Zabinsky ZB (2006) Addressing capacity uncertainty in resource-constrained assignment problems. Comput Oper Res 33:724โ745
Trick M (1992) Aย linear relaxation heuristic for the generalized assignment problem. Nav Res Logist 39:137โ151
Trick MA (1994) Scheduling multiple variable-speed machines. Oper Res 42(2):234โ248
Wilson JM (1997) Aย genetic algorithm for the generalised assignment problem. Jย Oper Res Soc 48:804โ809
Wilson JM (2005) An algorithm for the generalized assignment problem with special ordered sets. Jย Heuristics 11:337โ350
Yagiura M, Ibaraki T, Glover F (2004) An ejection chain approach for the generalized assignment problem. INFORMS J Comput 16:133โ151
Yagiura M, Ibaraki T, Glover F (2006) Aย path relinking approach with ejection chains for the generalized assignment problem. Eur J Oper Res 169:548โ569
Yagiura M, Yamaguchi T, Ibaraki T (1998) Aย variable depth search algorithm with branching search for the generalized assignment problem. Optim Method Softw 10:419โ441
Yagiura M, Yamaguchi T, Ibaraki T (1999) Aย variable depth search algorithm for the generalized assignment problem. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics; Advances and Trends in Local Search paradigms for Optimization, Kluwer, Boston, ppย 459โ471
Zhang CW, Ong HL (2007) An efficient solution to biobjective generalized assignment problem. Adv Eng Softw 38:50โ58
Zimokha VA, Rubinshtein MI (1988) R & d planning and the generalized assignment problem. Autom Remote Control 49:484โ492
Download references
Author information
Authors and affiliations.
Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA
O. Erhun Kundakciogluย &ย Saed Alizamir
You can also search for this author in PubMed ย Google Scholar
Editor information
Editors and affiliations.
Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA
Christodoulos A. Floudas
Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA
Panos M. Pardalos
Rights and permissions
Reprints and permissions
Copyright information
ยฉ 2008 Springer-Verlag
About this entry
Cite this entry.
Kundakcioglu, O.E., Alizamir, S. (2008). Generalized Assignment Problem . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_200
Download citation
DOI : https://doi.org/10.1007/978-0-387-74759-0_200
Publisher Name : Springer, Boston, MA
Print ISBN : 978-0-387-74758-3
Online ISBN : 978-0-387-74759-0
eBook Packages : Mathematics and Statistics Reference Module Computer Science and Engineering
Share this entry
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Stack Exchange Network
Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
How to solve large scale generalized assignment problem
I am looking for a way to solve a large scale Generalized assignment problem (To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of $=$ ). Here, $m$ is the number of agents and $n$ is the number of tasks. $$ \begin{aligned} &\text{maximize} && \sum_{i}^{m} \sum_{j}^{n} p_{ij}x_{ij} \\\ &\text{subject to} && \sum_{j}^{n} w_{ij}x_{ij} \le t_{i} &&& \forall i \\\ & && \sum_{i}^{m} x_{ij} \le 1 &&& \forall j \\\ & && x_{ij} \in \{0, 1\} \end{aligned} $$
- $m \le 1,000$
- $n \le 10,000,000$
- $p_{ij} \le 1,000$
- $w_{ij} \le 1,000$
- $t_i \le 200,000$
- valid agent-task pair(i.e. number of non zero $p_{ij}$ ) $\le 200,000,000$
- time limit : 6 hours
Generalized assignment problem is NP-hard, so I'm not trying to find an exact solution. Are there any approximation algorithm or heuristic to solve this problem?
Also, are there any other approaches to solving large scale NP-hard problems? For example, I was wondering if it is possible to reduce the number of variables by clustering agents or tasks, but I did not find such a method.
- assignment-problem
- $\begingroup$ All else failing, there is the greedy heuristic: sort the $p_{ij}$ in descending order, then make assignments in that order, tracking the remaining capacity of each agent and skipping assignments that would exceed that capacity. I did not put this in as an answer because it is such a low hanging fruit. $\endgroup$ – prubin ♦ Commented Jul 29, 2021 at 18:13
- $\begingroup$ The problem that you wrote is not exactly the Generalized Assignment Problem, because the second set of constraints has $\le$ instead of $=$. This makes the problem much easier since finding a feasible solution is not an issue anymore in this case. Is it what you meant to write? $\endgroup$ – fontanf Commented Jul 29, 2021 at 20:22
- $\begingroup$ @prubin Thank you. If there is no other way, I will use greedy algorithm. $\endgroup$ – user5966 Commented Jul 30, 2021 at 6:02
- $\begingroup$ @fontanf Yes, I'm trying to solve the relaxation of the Generalized assignment problem. I've added this to the post $\endgroup$ – user5966 Commented Jul 30, 2021 at 6:11
2 Answers 2
The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the literature have $m = 80$ and $n = 1600$ . Most algorithms designed for these instances won't be suitable for you.
What seems the most relevant in your case are the polynomial algorithms described in "Knapsack problems: algorithms and computer implementations" (Martello et Toth, 1990):
- Greedy: sort all agent-task pairs according to a given criterion, and then assign greedily from best to worst the unassigned tasks. Complexity: $O(n m \log (n m))$
- Regret greedy: for all tasks, sort its assignments according to a given criterion. At each step, assign the task with the greatest difference between its best assignment and its second-best assignment, and update the structures. Complexity: $O(n m \log m + n^2)$
Various sorting criteria have been proposed: pij , pij/wij , -wij , -wij/ti ... -wij and -wij/ti are more suited for the case where all items have to be assigned. In your case pij and pij/wij might yield good results
Then, they propose to try to shift each task once to improve the solution. With at most one shift per task, the algorithms remain polynomial, but you can try more shifts if you have more time.
Note that these algorithms might be optimized if not all pairs are possible, as you indicate in your case.
I have some implementations here for the standard GAP (and a min objective). You can try to play with them to get an overview of what might work or not in your case
You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP and simulated annealing would be possibilities. Tabu search is popular with some people, but the memory requirements of maintaining a table of tabu solutions might be prohibitive. I'm fond of genetic algorithms, but I think we can rule out a GA (or other "evolutionary" metaheuristic) based on memory considerations. Personally, I'd be tempted to check out GRASP first.
Your Answer
Sign up or log in, post as a guest.
Required, but never shown
By clicking โPost Your Answerโ, you agree to our terms of service and acknowledge you have read our privacy policy .
Not the answer you're looking for? Browse other questions tagged heuristics assignment-problem or ask your own question .
- Featured on Meta
- Bringing clarity to status tag usage on meta sites
- We've made changes to our Terms of Service & Privacy Policy - July 2024
- Announcing a change to the data-dump process
Hot Network Questions
- Ai-Voice cloning Scam?
- A burning devil shape rises into the sky like a sun
- Short story in which in which "aliens" from the future appear at a man's door
- When is internal use internal (considering licenses and their obligations)?
- The minimal Anti-Sudoku
- How to declutter a mobile app home screen with a floating “Create Video” component?
- Why are these simple equations so slow to `Solve`?
- Will The Cluster World hold onto an atmosphere for a useful length of time without further intervention?
- Did Newton predict the deflection of light by gravity?
- Argument of Complex Numbers with unknown values
- how to include brackets in pointform latex
- Do space stations have anything that big spacecraft (such as the Space Shuttle and SpaceX Starship) don't have?
- Is there a plurality of persons in the being of king Artaxerxes in his use of the pronoun "us" in Ezra 4:18?
- Justification for the Moral Ought
- Can you bring a cohort back to life?
- Cutting a 27×27 square into incomparable rectangles
- "Undefined" when attempting analytical expression for a RegionIntersection and its Area in V14.0
- Would several years of appointment as a lecturer hurt you when you decide to go for a tenure-track position later on?
- Should I pay off my mortgage if the cash is available?
- A post-apocalyptic short story where very sick people from our future save people in our timeline that would be killed in plane crashes
- Is it possible that fundamental truths about the origins of our reality will never be discovered?
- Short story about a committee planning to eliminate 1 in 10 people
- Vim macro to mapping
- Writing a Puzzle Book: Enigmatic Puzzles
Stack Exchange Network
Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
Algorithms for a many-to-many generalized assignment problem
I can't seem to find any literature on algorithms which can be used to solve a many-to-many generalized assignment problem (GAP), i.e. models where not only can more tasks be assigned to one agent, but multiple agents can also be assigned to one task (one-to-one and one-to-many AP's are discussed in a paper by Pentico). I know next-to-nothing of assignment problems, but I came upon a problem like this during my research and would like to know more about how to solve them. Is it possible that such a many-to-many GAP is known under another name, or is there a different reason why so few literature on it can be found?
Pentico, D. Assignment Problems: A Golden Anniversary Survey . European Journal Of Operational Research (2007); 176 (2):774-793.
- data-analysis
![online generalized assignment problem Parker's user avatar](https://i.sstatic.net/vTHal.png?s=64)
- 1 $\begingroup$ Hi GerritJan. Welcome to Scicomp! :) Are you familiar with thes lagrangian heuristic for the generalized assignment problem? sciencedirect.com/science/article/pii/S0898122110002609 or irma-international.org/viewtitle/58969 or crcnetbase.com/doi/abs/10.1201/9781420010749.ch48 ? $\endgroup$ – Paul Commented May 2, 2012 at 13:42
- 1 $\begingroup$ It seems to me that the case of assigning portions of a task to multiple agents can be modelled, at least in cases where costs are linearly apportioned, by treating the one task as if it were instead multiple subtasks. Without more details it's hard to know how your problems might be more "general" than generalized assignment problems. The Wikipeida article has some good exposition and links to a couple of references on the topic. $\endgroup$ – hardmath ♦ Commented May 3, 2012 at 1:53
- $\begingroup$ Thanks, @Paul. I will look into the papers, although they seem to be rather complicated to my untrained eye. Then again, I suspect the problem is complicated, and I will probably have to do some simplifying. hardmath, my problem is basically that of distributing energy in a network: supply- and demandnodes need to be matched using the (weighted) connections between them, in the most optimal way, with a minimum use of supply to fulfill all demand. Of course, additional constraints can be used, like maximal capacity on the connections, etc. $\endgroup$ – Gerrit Jan Commented May 3, 2012 at 7:19
- 1 $\begingroup$ @GerritJan: It's an np-hard problem, so it will require an approximation scheme. If you need a good approximation, your algorithm may have to be a bit complex. $\endgroup$ – Paul Commented May 3, 2012 at 19:08
- 2 $\begingroup$ @GerritJan: It means that the exact 'optimal' solution can only be guaranteed by checking all possible configurations. These possible solutions grow (at least) exponentially over time, making even relatively modest size problems virtually impossible to solve exactly in a reasonable amount of time. $\endgroup$ – Paul Commented May 4, 2012 at 13:57
2 Answers 2
Your problem doesn't seem to be, "that the sum of the "agents" have to supply exactly a discrete portion of energy or nothing for each single demand ...", right? Or you did not understand me. So I'll try to describe my problem better, also because I found a solution.
In my problem, I have a set of agents where each one has a budget of certain resources, who can share the cost of tasks, which should be "executed" 1 time or not (many-to-many-assignment without the need to "execute" every task). It means: the sum of partial solutions of agents for task x should be less or equal to cost of task x. The objective is to find the set of tasks with most value which agents can pay.
I'm working with gams software so i describe it in gams-style: set a agents, t tasks parameter cost(t), value(t) parameter resources(a)
positive variable y(a,t) (non-int), part of agent a for cost of task t objective:
As I wrote, I had a solution but didn't know how to separate partial task solutions. But now I found out that I can build a constraint with a
binary variable z(t)
taskcost_bin_constraint z(t) =e= sum(a, y(a,t)) / cost(t);
sum(a, y(a,t)) / cost(t) in the equation formulation is something between 0 and 1 and by this constraint, z is 0 for all less than 1 and 1 for 1. with this taskcost_bin_constraint objective would be:
I was wondering but this works and gives me better solutions under the constraint, to build a task full or not.
Maybe you can also add such a constraint? A Constraint to fullfill the demands exactly, expressed in a expression with value between 0 and 1.
There is a deterministic annealing algorithm which solves the one-to-one assignment problem or equivalently the dyadic matrix partition problem.
However instead of using integer [0, 1] values one can use fractional values (so the algorithm remains the same) or even extend it to handle more than one assignment (by adding an inner loop and eseentially the matrix becomes a hyper-dimensional array or tensor)
The paper is here: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf
Your Answer
Sign up or log in, post as a guest.
Required, but never shown
By clicking โPost Your Answerโ, you agree to our terms of service and acknowledge you have read our privacy policy .
Not the answer you're looking for? Browse other questions tagged algorithms data-analysis or ask your own question .
- Featured on Meta
- Bringing clarity to status tag usage on meta sites
- We've made changes to our Terms of Service & Privacy Policy - July 2024
- Announcing a change to the data-dump process
Hot Network Questions
- Is there any point "clean-installing" on a brand-new MacBook?
- Can a Statute of Limitations claim be rejected by the court?
- How to interpret coefficients of logistic regression using natural cubic splines?
- What is Causing This Phenomenon? Is it the Geometry Package?
- How to declutter a mobile app home screen with a floating “Create Video” component?
- Secret super people
- Suitable tool bag for vintage centre pull rim brake bike
- How do you determine maximum frequency of AD574A 12-bit ADC?
- Is Psalm 107:4-7 ascribing the forty years of wandering in the wilderness to Moses refusing to ask for directions?
- Claims of "badness" without a moral framework?
- Did the Space Shuttle weigh itself before deorbit?
- Density of perfect numbers
- What's the polarity of this electrolytic capacitor symbol?
- Why does Air Force Two lack a tail number?
- How many advancements can a Root RPG character get before running out of options to choose from in the advancement list?
- How to Handle a Discovery after a Masters Completes
- Can you bring a cohort back to life?
- Short story in which in which "aliens" from the future appear at a man's door
- Is there an integer that serves as the short leg of a primitive Pythagorean triple, the long leg of another, and the hypotenuse of a third?
- In "Take [action]. When you do, [effect]", is the action a cost or an instruction?
- Meaning of 皮がたわむ here
- The minimal Anti-Sudoku
- Meaning of 折れ込む here
- What are those bars in subway train or bus called?
This paper is in the following e-collection/theme issue:
Published on 14.8.2024 in Vol 26 (2024)
Impact of an Online Discussion Forum on Self-Guided Internet-Delivered Cognitive Behavioral Therapy for Public Safety Personnel: Randomized Trial
Authors of this article:
![online generalized assignment problem Author Orcid Image](https://asset.jmir.pub/assets/static/images/Orcid-ID-Logo-Colour.png)
Original Paper
- Hugh C McCall 1, 2 , MA ;
- Heather D Hadjistavropoulos 1, 2 , PhD
1 Department of Psychology, University of Regina, Regina, SK, Canada
2 PSPNET, University of Regina, Regina, SK, Canada
Corresponding Author:
Heather D Hadjistavropoulos, PhD
Department of Psychology
University of Regina
3737 Wascana Pkwy
Regina, SK, S4S 0A2
Phone: 1 306 585 5133
Email: [email protected]
Background: Internet-delivered cognitive behavioral therapy (ICBT) is an effective and accessible treatment for various mental health concerns. ICBT has shown promising treatment outcomes among public safety personnel (PSP), who experience high rates of mental health problems and face barriers to accessing other mental health services. Client engagement and clinical outcomes are better in ICBT with therapist guidance, but ICBT is easier to implement on a large scale when it is self-guided. Therefore, it is important to identify strategies to improve outcomes and engagement in self-guided ICBT and other self-guided digital mental health interventions. One such strategy is the use of online discussion forums to provide ICBT clients with opportunities for mutual social support. Self-guided interventions accompanied by online discussion forums have shown excellent treatment outcomes, but there is a need for research experimentally testing the impact of online discussion forums in ICBT.
Objective: We aimed to evaluate a transdiagnostic, self-guided ICBT intervention tailored specifically for PSP (which had not previously been assessed), assess the impact of adding a therapist-moderated online discussion forum on outcomes, and analyze participants’ feedback to inform future research and implementation efforts.
Methods: In this randomized trial, we randomly assigned participating PSP (N=107) to access an 8-week transdiagnostic, self-guided ICBT course with or without a built-in online discussion forum. Enrollment and participation were entirely web-based. We assessed changes in depression, anxiety, and posttraumatic stress as well as several secondary outcome measures (eg, treatment engagement and satisfaction) using questionnaires at the pre-enrollment, 8-week postenrollment, and 20-week postenrollment time points. Mixed methods analyses included multilevel modeling and qualitative content analysis.
Results: Participants engaged minimally with the forum, creating 9 posts. There were no differences in treatment outcomes between participants who were randomly assigned to access the forum (56/107, 52.3%) and those who were not (51/107, 47.7%). Across conditions, participants who reported clinically significant symptoms during enrollment showed large and statistically significant reductions in symptoms ( P <.05 and d >0.97 in all cases). Participants also showed good treatment engagement and satisfaction, with 43% (46/107) of participants fully completing the intervention during the course of the study and 96% (79/82) indicating that the intervention was worth their time.
Conclusions: Previous research has shown excellent clinical outcomes for self-guided ICBT accompanied by discussion forums and good engagement with those forums. Although clinical outcomes in our study were excellent across conditions, engagement with the forum was poor, in contrast to previous research. We discuss several possible interpretations of this finding (eg, related to the population under study or the design of the forum). Our findings highlight a need for more research evaluating the impact of online discussion forums and other strategies for improving outcomes and engagement in self-guided ICBT and other digital mental health interventions.
Trial Registration: ClinicalTrials.gov NCT05145582; https://clinicaltrials.gov/study/NCT05145582
Introduction
Internet-delivered cognitive behavioral therapy (ICBT) is a psychological treatment in which clients learn evidence-based cognitive behavioral therapy treatment strategies via web-based modules, often with therapist guidance via email or phone. Hundreds of randomized trials have demonstrated that ICBT is similarly effective to face-to-face psychotherapies for treating depression and anxiety [ 1 ]. There are 2 key advantages of ICBT and other digital mental health interventions (DMHIs): the ability of clients to access them privately and conveniently at practically any time and location [ 2 - 4 ] and the tendency for DMHIs to require less therapist time per client than traditional face-to-face psychotherapies [ 2 , 4 ].
ICBT is sometimes offered in a purely self-guided format (ie, without a therapist). Meta-analyses have shown that self-guided ICBT is at least slightly less effective than therapist-guided ICBT; this assertion is based on differences in effect sizes observed in separate meta-analyses of guided [ 1 ] and self-guided [ 5 , 6 ] ICBT, meta-analyses including subgroup analyses of both guided and self-guided ICBT [ 7 - 9 ], a meta-regression in which human contact predicted more favorable ICBT outcomes [ 10 ], a meta-analysis of randomized trials directly comparing guided and self-guided ICBT [ 11 ], and an individual-participant meta-analysis evaluating both guided and self-guided ICBT for depression [ 12 ]. In addition, client engagement with self-guided ICBT and other self-guided DMHIs tends to be low [ 13 - 15 ], particularly in real-world observational research, where completion rates were found in one systematic review to range from 0.5% to 28.6% [ 14 ]. However, self-guided ICBT and other self-guided DMHIs can be implemented on a large scale with minimal human or financial inputs required [ 7 , 16 ], making them cost-effective [ 17 ] and—many have argued—justifiable despite their tendency to be less effective than therapist-guided DMHIs or face-to-face psychotherapies [ 16 , 18 ].
There appears to be a growing consensus that DMHIs can be designed to be more engaging for clients [ 5 , 19 - 21 ], which may have particular implications for mitigating the problem of low engagement in self-guided DMHIs. The persuasive system design framework [ 22 ] describes 28 specific design principles for improving engagement divided into four categories: (1) primary task support principles, which facilitate completion of treatment tasks (eg, tailoring content for specific user groups and presenting complex tasks in a series of simple steps); (2) dialogue support principles, which facilitate dialogue between an intervention and its users (eg, automated praise, reminders, or virtual rewards); (3) system credibility support principles, which help ensure that users perceive interventions as credible (eg, endorsements from credible third parties and inclusion of experts in the design process); and (4) social support principles, which enable users to support each other in their use of an intervention (eg, opportunities for users to support and learn from each other). Systematic reviews and meta-analyses have shown that persuasive design characteristics can predict treatment engagement [ 20 ] and symptom change [ 5 ], but research assessing the impact of specific persuasive design principles is limited.
Online discussion forums facilitate social support principles of persuasive design. Previous research suggests that they may help support engagement and outcomes in self-guided DMHIs. For example, participants in forum-only control conditions across several studies have demonstrated promising outcomes [ 23 - 26 ], prompting the authors of one paper to conclude that they “could be regarded as an intervention” in and of themselves [ 23 ]. In total, 3 randomized trials have shown that self-guided ICBT [ 27 , 28 ] or self-guided bibliotherapy [ 3 ] accompanied by an online discussion forum exhibited equivalent outcomes to those of therapist-guided ICBT. Another randomized trial experimentally demonstrated that adding an online discussion forum to guided ICBT improved engagement [ 29 ]. Together, these studies suggest that forums could help improve engagement and outcomes in ICBT—potentially bridging the engagement and efficacy gap between guided and self-guided ICBT—but there are no previous randomized trials experimentally evaluating the impact of a forum on engagement and outcomes in self-guided ICBT.
In 2019, a clinical research unit called PSPNET was founded to develop, deliver, and conduct research on free ICBT interventions tailored specifically for Canadian first responders and other public safety personnel (PSP), who frequently experience potentially psychologically traumatic events [ 30 ], report high rates of mental health problems [ 31 ], and face unique barriers to accessing mental health care (eg, stigma within their workplaces) [ 32 , 33 ]. At the time this study was conducted, PSPNET offered 2 therapist-guided ICBT interventions to Canadian PSP—one transdiagnostic and the other posttraumatic stress disorder (PTSD) specific—both of which have shown promising outcomes with respect to symptom change, engagement, and treatment satisfaction [ 34 - 36 ]. However, at the time of this study, PSPNET was unable to offer guided ICBT services to PSP in all Canadian provinces and territories, highlighting an opportunity to develop a self-guided ICBT intervention that could be delivered with minimal resources required to PSP anywhere in Canada. No previous research has evaluated self-guided ICBT tailored specifically for PSP.
Objectives and Hypotheses
Broadly speaking, we designed this study to evaluate self-guided ICBT among Canadian PSP while addressing several questions concerning the role of online discussion forums in self-guided ICBT. Specifically, we sought to address the following four objectives:
- To evaluate transdiagnostic, self-guided ICBT tailored for PSP with respect to treatment engagement, outcomes, and satisfaction.
- To evaluate whether adding an online discussion forum to transdiagnostic, self-guided ICBT tailored for PSP would improve engagement and outcomes.
- To evaluate whether participant engagement in the online discussion forum would moderate treatment outcomes.
- To conduct a mixed methods analysis of participant feedback on the discussion forum.
We hypothesized that participants in both conditions would experience at least small to moderate reductions in symptoms of depression, anxiety, and posttraumatic stress, consistent with recent meta-analytic evidence [ 5 , 6 ]. Second, we hypothesized that participants randomly assigned to receive access to an online discussion forum would show greater engagement and more favorable treatment outcomes than those randomly assigned to receive ICBT without a discussion forum.
Study Design
We used a randomized trial design with 2 conditions: an ICBT plus peer support forum condition and an ICBT-only condition. Participants in both conditions were given free access to a self-guided ICBT program called the Self-Guided PSP Wellbeing Course . For participants in the ICBT plus peer support forum condition, but not for those in the ICBT-only condition, this ICBT course included a built-in online discussion forum. Participants were not blinded to their own condition as it is not possible to hide therapy content from those receiving therapy, but the experimental manipulation was described only in general terms (ie, without reference to forums) such that participants were blind to how the condition to which they were assigned differed from the condition to which they were not assigned. We adopted a simple randomization approach [ 37 ], which we implemented via a random number generator with a 1:1 ratio. We registered the methodological protocol for this research on ClinicalTrials.gov (ID NCT05145582) and made 2 deviations from it. First, we removed the Sheehan Disability Scale [ 38 ] from our planned outcome measures because we were unable to obtain permission to use it. Second, we ultimately carried out our primary quantitative analyses using multilevel modeling (MLM) instead of generalized estimating equations, as we had originally planned, because a paper was published during the course of this research that provided a compelling rationale and detailed recommendations for using MLM in treatment-control pretest-posttest-follow-up study designs [ 39 ]. We followed the CONSORT (Consolidated Standards of Reporting Trials) guidelines [ 40 ] in reporting the findings of this research. This research was conducted within the context of author HCM’s doctoral dissertation, and we would refer interested readers to this dissertation (expected to be publicly available in or around October 2024) for further details about this research.
This study was conducted in Canada, where publicly funded mental health services have not met public demand, leading many Canadians to access private mental health care instead [ 41 ]. Canadians have access to DMHIs through various Canadian organizations [ 42 ]. There are also thousands of mental health–related phone apps and websites available in Canada and other countries [ 43 ], but many of these services are not empirically supported. All research activities pertaining to this study were carried out at the University of Regina in Saskatchewan, Canada.
Participants, Recruitment, and Enrollment
A power analysis indicated that a minimum of 110 participants would be required to achieve adequate power to detect moderate between-group differences (see Multimedia Appendix 1 [ 3 , 5 , 8 , 27 , 34 , 44 - 47 ] for details on our sample size planning). Participants were informed about this research via paid social media advertisements (ie, Twitter [subsequently rebranded X] and Facebook), emails forwarded to PSP by leaders of PSP organizations, presentations to PSP organizations by author HCM and PSPNET’s clinicians, and word of mouth. To be eligible to take part, prospective participants were required to self-report (1) being aged ≥18 years; (2) residing in Canada; (3) working, volunteering, or having previously worked or volunteered as a PSP; (4) being able to access the internet via a computer; and (5) not experiencing significant ongoing concerns related to alcohol or drug use, psychotic symptoms, or manic symptoms.
Prospective participants accessed this study through a web page on PSPNET’s website, which provided information about the study. Upon reviewing a consent form and consenting to participate, they accessed a series of eligibility screening questionnaires through Qualtrics (Qualtrics International Inc). We contacted prospective participants by email to inform them of their eligibility, and eligible participants were asked to confirm their intent to take part in the study, after which they were randomly assigned to 1 of the 2 conditions and provided with a temporary password to access the version of the Self-Guided PSP Wellbeing Course (ie, with or without the peer support forum) to which they had been assigned. All randomization and enrollment procedures were carried out by author HCM and research assistant Julia Gregory (see the Acknowledgments section). Recruitment took place between December 6, 2021, and September 26, 2022.
Primary Outcome Measures
Patient health questionnaire–9.
The Patient Health Questionnaire–9 (PHQ-9) is a psychometrically sound, 9-item questionnaire assessing depressive symptoms [ 48 , 49 ]. Possible total scores range from 0 to 27, and a score of ≥10 suggests that a respondent’s symptoms are clinically significant [ 50 ].
Generalized Anxiety Disorder–7
The Generalized Anxiety Disorder–7 (GAD-7) is a 7-item questionnaire assessing generalized anxiety that has demonstrated strong psychometric properties [ 49 , 51 ]. Total scores can range from 0 to 21, with a score of ≥10 suggesting clinically significant symptoms [ 49 , 51 ].
PTSD Checklist for DSM-5
PTSD Checklist for DSM-5 (PCL-5) is a psychometrically sound questionnaire assessing PTSD symptoms [ 52 ]. Responses to its 20 items sum to a total score ranging from 0 to 80, and a score of ≥33 indicates that a respondent likely meets criteria for a PTSD diagnosis [ 53 , 54 ].
Secondary Outcome Measures
Brief resilience scale.
The Brief Resilience Scale (BRS) is a 6-item questionnaire measure of resilience that has shown good psychometric properties [ 55 , 56 ]. Each item has 5 response options with associated numerical values ranging from 1 to 5, and a higher mean score across items indicates greater resilience.
Flourishing Scale
The Flourishing Scale (FS) is an 8-item questionnaire assessing flourishing across various domains of life (eg, relationships, meaning and purpose, and feeling of competence). It has demonstrated good psychometric properties [ 57 , 58 ]. Total scores can range from 8 to 56, with greater scores indicating a greater degree of flourishing.
Treatment Satisfaction Questionnaire
We administered a bespoke questionnaire designed to assess treatment satisfaction and solicit feedback on the Self-Guided PSP Wellbeing Course through a mix of yes or no, Likert-scale, and open-ended text response items. For participants in the ICBT plus peer support forum condition, the Treatment Satisfaction Questionnaire included several additional items pertaining to the forum. Open-ended questions about both the course and the forum were designed to solicit both positive and constructive feedback.
Adapted Session Rating Scale
We administered a modified version of the Session Rating Scale (SRS), a 4-item questionnaire originally designed to assess client perspectives on the quality of the therapeutic alliance in face-to-face therapy [ 59 ]. It has good psychometric qualities [ 60 , 61 ]. Items are rated on a 7-point Likert scale from 0 ( absolutely disagree ) to 6 ( absolutely agree ) and assess the therapeutic bond, goal agreement, task agreement, and overall alliance quality. Following an approach taken in another study [ 62 ], we adapted the SRS to measure patient-program alliance.
Program Use Questionnaire
We administered a brief bespoke questionnaire assessing engagement with the Self-Guided PSP Wellbeing Course and, if applicable, the peer support forum. Specifically, this questionnaire was designed to assess effort put into the course; the perceived helpfulness of the course; and, if applicable, use and perceived helpfulness of the peer support forum. Program use patterns were also assessed via automatic collection of program use data (eg, number of lessons and additional resources accessed).
Health Service Use Questionnaire
We also administered a bespoke questionnaire to assess use of health care services for mental health challenges during eligibility screening and at 8 and 20 weeks after enrollment. In the interest of brevity, and because this questionnaire is peripheral to the primary objectives of this study, we do not describe the outcomes of this questionnaire in this paper.
Pre-Enrollment Measures
During eligibility screening, we administered a bespoke participant information questionnaire assessing demographic, occupational, and clinical characteristics; an ICBT feedback questionnaire assessing pre-enrollment knowledge and attitudes toward ICBT; the Credibility/Expectancy Questionnaire (CEQ) [ 63 ]; the Alcohol Use Disorders Identification Test [ 64 ]; and the Drug Use Disorders Identification Test [ 65 ].
Administration of Measures
During eligibility screening, we administered the PHQ-9, GAD-7, PCL-5, BRS, FS, participant information questionnaire, ICBT feedback questionnaire, CEQ, Alcohol Use Disorders Identification Test, and Drug Use Disorders Identification Test. At 2, 4, 6, and 8 weeks after enrollment, we administered the Program Use Questionnaire. At 8 weeks after enrollment, we also administered the PHQ-9, GAD-7, PCL-5, BRS, FS, and Treatment Satisfaction Questionnaire. At 20 weeks after enrollment, we administered the PHQ-9, GAD-7, PCL-5, BRS, and FS. Our research team encouraged participants to complete the questionnaires via emails and phone calls but did not urge participants to use the Self-Guided PSP Wellbeing Course .
Intervention
The Self-Guided PSP Wellbeing Course is an 8-week self-guided, transdiagnostic ICBT program that can be accessed through a web browser. It includes 5 core lessons, each consisting of a welcome video, a series of slides with instructive text and diagrams, an audio file covering the same clinical content as the lesson slides, illustrative case stories, frequently asked questions, downloadable homework activities called “DIY Guides,” and quotes from previous clients. These lessons included an introduction to the cognitive behavioral model and psychoeducation to help participants recognize and understand their symptoms (lesson 1); skills to help participants recognize and challenge unhelpful thoughts (lesson 2); skills for managing physiological underarousal and overarousal symptoms (lesson 3); skills for managing behavioral symptoms (lesson 4); and strategies for maintaining treatment gains, setting goals, and preventing future relapses (lesson 5). The course also included 14 additional resources covering a wide range of topics (eg, assertiveness, physical pain, and intimate relationships) and automated email reminders to encourage engagement.
The Self-Guided PSP Wellbeing Course is effectively a self-guided version of a previously developed therapist-guided ICBT course called the PSP Wellbeing Course [ 34 , 36 ]; aside from the provision of therapist guidance in the latter but not the former, the courses are practically identical. PSPNET developed the PSP Wellbeing Course by tailoring an existing ICBT program called the Wellbeing Course to meet the needs of Canadian PSP based on feedback provided by Canadian PSP in a series of interviews, focus groups, and questionnaires [ 33 , 66 ]. The original Wellbeing Course was initially developed by the eCentreClinic at Macquarie University, Australia, and has since shown excellent outcomes among the general population in Australia [ 67 ] and Canada [ 68 ].
Discussion Forum
The peer support forum was built into the Self-Guided PSP Wellbeing Course . It included 11 sections (eg, one for each of the 5 lessons, one for discussing families and relationships, and one for discussing workplace issues). It was monitored daily and moderated as required each business day by author HCM, who posed questions to spark discussion and responded to participants’ posts.
Ethical Considerations
This study was approved by the University of Regina Research Ethics Board (file 2021-130). Before taking part, all participants were provided with an informed consent form, which described the following: the objectives of the research, the research team, what participation would entail (ie, the intervention and questionnaires), possible risks and benefits of participating, project funding, considerations regarding concurrent mental health treatments, right to withdraw, limits to confidentiality, risks to privacy, precautions to improve security of participant information (both PSPNET’s precautions and precautions that participants could take), uses of participants’ data (ie, eligibility determination and research), information on accessing research results, a statement indicating that participants would not be compensated for taking part, and an invitation to contact our team with any questions or concerns. All participant data were deidentified before analysis. Due to ethical concerns related to the exclusion of individuals reporting suicidal ideation from DMHI research [ 69 ], we tried to refer prospective participants reporting suicidal ideation to more intensive services and clarified that the Self-Guided PSP Wellbeing Course is not a crisis service, but we allowed them to participate if they met the eligibility criteria.
Quantitative Data Analyses
We carried out all quantitative analyses using SPSS (version 28; IBM Corp). We did not statistically test for group differences in pre-enrollment variables as it is not meaningful to test the probability that group differences occurred by chance when it is already known—due to random assignment—that they did [ 70 ]. Instead, we inspected the magnitude of group differences and planned to conduct sensitivity analyses to assess the impact of marked differences should we observe any. We compared changes in scores on the PHQ-9, GAD-7, PCL-5, FS, and BRS across conditions using an MLM approach recommended by Sharpe and Cribbie [ 39 ]. We used an intention-to-treat approach [ 71 ] including all participants in the analyses, and we accounted for missing data using the restricted maximum likelihood estimation method, which previous research suggests is preferable to maximum likelihood estimation for MLM when random effects are included [ 72 ]. Each model was run using a random intercept and fixed effects of group, time (as a categorical variable), and the interaction between group and time. We used a variance components covariance structure [ 73 ]. We also produced a G matrix for each model consistent with the recommendations by Sharpe and Cribbie [ 39 ]. We used scatterplots and histograms to test the assumptions of linearity, homoscedasticity of residuals, and normality of residuals [ 74 ]. For each of the 5 outcome variables, we conducted one model for the entire sample and one model for the subset of participants with clinically significant scores at the pre-enrollment time point, which we defined using established cutoff scores for the PHQ-9 (≥10), GAD-7 (≥10), or PCL-5 (≥33) and scores in the lower 3 quartiles on the FS (<48) and BRS (<4.0). Therefore, we ran 10 models in total.
In each of the 10 MLM models, we conducted 5 contrasts. In total, 2 contrasts were designed to assess for interactions between group and time—that is, to identify any differences between groups with respect to changes in dependent variables over time—including one contrast for the period between the pre-enrollment time point and 8 weeks after beginning treatment and one for the period between the pre-enrollment time point and 20 weeks after beginning treatment. We collapsed the 2 groups for 3 additional contrasts to determine whether changes in questionnaire scores over time were statistically significant—one contrast for the period between the pre-enrollment time point and 8 weeks after beginning treatment, one for the period between the pre-enrollment time point and 20 weeks after beginning treatment, and one for the period between 8 weeks and 20 weeks after beginning treatment. These latter 3 contrasts were designed to assess whether participants in the Self-Guided PSP Wellbeing Course experienced significant changes in their mental health.
Finally, in each of the 10 MLM models, we investigated the effects of five covariates on changes in questionnaire scores over time: (1) the number of lessons that participants accessed, (2) the number of additional resources that participants accessed, (3) CEQ credibility scores, (4) CEQ expectancy scores, and (5) gender. These analyses are not central to the objectives of this study but may be of interest to some readers; accordingly, a rationale for the inclusion of these specific covariates, methods and results pertaining to our covariate analyses, and a brief discussion of the findings of those analyses are shown in Multimedia Appendix 2 [ 63 , 75 - 80 ].
In addition to the MLM models, we used 2-tailed independent-sample t tests and chi-square tests to assess for group differences in treatment satisfaction and program use. Upon observing possible group differences in rates of questionnaire completion, we conducted additional (non-prespecified) chi-square tests to evaluate their significance.
Qualitative Data Analyses
We conducted qualitative analyses using a content analysis approach to explore participant feedback on the peer support forum and the Self-Guided PSP Wellbeing Course in general [ 81 ]. After removing identifying information from the data, author HCM identified categories using a descriptive, inductive approach and grouped those categories into overarching themes. Given the relatively small amount of data, this was carried out using an Excel (Microsoft Corp) spreadsheet. The initial codebook was refined through meeting with author HDH and Dr Janine Beahm (see the Acknowledgments section).
It is a common practice for researchers using qualitative methods to engage in reflexivity, which is a practice of reflection on how the researchers’ positionality might affect the process or outcomes of qualitative research [ 82 ]. Being neither PSP nor ICBT clients, the authors do not identify as members of the population under study, potentially granting the authors a degree of neutrality in describing participants’ reported experiences but also potentially impeding their ability to fully understand those experiences [ 82 ]. In addition, the authors held certain attitudes and beliefs (eg, that ICBT can be helpful for many people and that forums may be able to enhance ICBT) that may have influenced the process and outcomes of this research. Nevertheless, we endeavored to minimize the risk of bias in this research by (1) including neutrally worded questions to solicit both positive and negative feedback; (2) conducting content analysis as descriptively as possible and avoiding even minor inferences and assumptions; (3) separating qualitative data from other data that could cause bias in coding (eg, demographic and clinical characteristics) before analysis; and (4) involving 3 researchers, as noted previously, in checking the accuracy of our coding.
Participants
Of the 188 prospective participants who completed the web-based screening, 153 (81.4%) were enrolled in the study and randomized, and 107 (56.9%) were included in our analyses. A flowchart displaying enrollment, program use, and questionnaire completion is shown in Figure 1 . Of note, Figure 1 shows that 36 participants in the ICBT-only condition completed symptom measures at 20 weeks after enrollment; one of these participants completed the PHQ-9 and GAD-7 but not the PCL-5. Participant characteristics are shown in Table 1 . Chi-square tests evidenced that the difference between conditions with respect to the proportion of participants who completed posttreatment questionnaires was statistically significant at 8 weeks (n=107, χ 2 1 =6.4, P =.01) but not at 20 weeks (n=107, χ 2 1 =0.5, P =.47).
![online generalized assignment problem online generalized assignment problem](https://asset.jmir.pub/assets/59cd728c40751d9e09475469da80c69f.png)
Characteristics | All participants | ICBT -only condition (n=51) | ICBT plus peer support forum condition (n=56) | |
Women | 62 (57.9) | 28 (54.9) | 34 (60.7) | |
Men | 45 (42.1) | 23 (45.1) | 22 (39.3) | |
Married, common-law marriage, or living with a partner | 78 (72.9) | 38 (74.5) | 40 (71.4) | |
Not married, in a common-law marriage, or living with a partner | 29 (27.1) | 13 (25.5) | 16 (28.6) | |
Has ≥1 children | 70 (65.4) | 36 (70.6) | 34 (60.7) | |
Has no children | 37 (34.6) | 15 (29.4) | 22 (39.3) | |
British Columbia | 23 (21.5) | 13 (25.5) | 10 (17.9) | |
Ontario | 21 (19.6) | 10 (19.6) | 11 (19.6) | |
Alberta | 15 (14) | 9 (17.6) | 6 (10.7) | |
New Brunswick | 12 (11.2) | 4 (7.8) | 8 (14.3) | |
Nova Scotia | 11 (10.3) | 4 (7.8) | 7 (12.5) | |
Prince Edward Island | 10 (9.3) | 5 (9.8) | 5 (8.9) | |
Saskatchewan | 8 (7.5) | 4 (7.8) | 4 (7.1) | |
Manitoba | 4 (3.7) | 0 (0) | 4 (7.1) | |
Newfoundland and Labrador | 1 (0.9) | 1 (2) | 0 (0) | |
Northwest Territories | 1 (0.9) | 1 (2) | 0 (0) | |
Quebec | 1 (0.9) | 0 (0) | 1 (1.8) | |
<100,000 residents | 72 (67.3) | 32 (62.7) | 40 (71.4) | |
≥100,000 residents | 35 (32.7) | 19 (37.3) | 16 (28.6) | |
No university degree | 56 (52.3) | 26 (51) | 30 (53.6) | |
University degree | 51 (47.7) | 25 (49) | 26 (46.4) | |
, n (%) | ||||
≥10 | 75 (70.1) | 37 (72.5) | 38 (67.9) | |
0-9 | 32 (29.9) | 14 (27.5) | 18 (32.1) | |
Police | 37 (34.6) | 19 (37.3) | 18 (32.1) | |
Corrections | 23 (21.5) | 10 (19.6) | 13 (23.2) | |
Paramedics or related emergency service | 16 (15) | 9 (17.6) | 7 (12.5) | |
Fire | 11 (10.3) | 5 (9.8) | 6 (10.7) | |
Communications (eg, 911 dispatch) | 7 (6.5) | 2 (3.9) | 5 (8.9) | |
Other | 13 (12.1) | 6 (11.8) | 7 (12.5) | |
Indigenous (ie, First Nations, Inuit, or Metis) | 7 (6.5) | 6 (11.8) | 1 (1.8) | |
White | 96 (89.7) | 42 (82.4) | 54 (96.4) | |
Other ethnic minority group | 3 (2.8) | 2 (3.9) | 1 (1.8) | |
Prefer not to answer | 1 (0.9) | 1 (2) | 0 (0) | |
20-29 | 7 (6.5) | 4 (7.8) | 3 (5.4) | |
30-39 | 27 (25.2) | 16 (31.4) | 11 (19.6) | |
40-49 | 47 (43.9) | 22 (43.1) | 25 (44.6) | |
50-59 | 21 (19.6) | 9 (17.6) | 12 (21.4) | |
60-69 | 5 (4.7) | 0 (0) | 5 (8.9) | |
Age (y), mean (SD) | 44.50 (9.28) | 42.97 (8.94) | 45.90 (9.45) |
a ICBT: internet-delivered cognitive behavioral therapy.
b PSP: public safety personnel.
Changes in Questionnaire Scores
We observed a common pattern of results across all 10 MLM models: (1) all statistical assumptions were met; (2) we did not identify statistically significant effects of group or group-by-time interactions ( P ≥.17 in all cases); (3) contrasts showed no effect of group on score change at 8 or 20 weeks for any measure; (4) there was a statistically significant and favorable effect of time (ie, scores on the PHQ-9, GAD-7, and PCL-5 decreased and scores on the FS and BRS increased over time); (5) contrasts showed statistically significant improvement in scores at 8 and 20 weeks for all measures; and (6) we identified residual variance, suggesting that models were likely missing predictor variables that could have helped account for estimates of dependent variables (which was expected given that covariates were tested separately via contrasts rather than being included in MLM models).
There were also some differences across MLM models. Certain contrasts for the PHQ-9 and PCL-5 showed further improvement in symptoms from 8 to 20 weeks. Further details of MLM results are reported in Table 2 (estimated means and percentage changes) and Table 3 (contrasts). Unaltered questionnaire scores observed among respondents at each time point are shown in Multimedia Appendix 3 [ 83 - 86 ].
Questionnaires and time points | Entire sample | Clinical subsamples | ||||||
Both conditions | ICBT only | ICBT plus peer support forum | Both conditions | ICBT only | ICBT plus peer support forum | |||
Pre-enrollment time point, estimated mean | 9.51 | 9.69 | 9.34 | 14.21 | 14.35 | 14.07 | ||
8 weeks, estimated mean (% change from pre-enrollment time point) | 7.26 (–23.7) | 6.96 (–28.2) | 7.53 (–19.4) | 9.58 (–32.6) | 9.86 (–31.3) | 9.31 (–33.9) | ||
20 weeks, estimated mean (% change from pre-enrollment time point) | 6.01 (–36.7) | 5.94 (–38.7) | 6.08 (–34.9) | 7.94 (–44.1) | 7.96 (–44.5) | 7.93 (–43.6) | ||
Pre-enrollment time point, estimated mean | 8.10 | 8.34 | 7.88 | 13.79 | 14.47 | 13.15 | ||
8 weeks, estimated mean (% change from pre-enrollment time point) | 6.19 (–23.5) | 5.92 (–29.0) | 6.44 (–18.3) | 8.71 (–36.9) | 9.08 (–37.3) | 8.35 (–36.5) | ||
20 weeks, estimated mean (% change from pre-enrollment time point) | 5.31 (–34.5) | 5.47 (–34.4) | 5.16 (–34.4) | 8.25 (–40.2) | 8.46 (–41.6) | 8.05 (–38.8) | ||
Pre-enrollment time point, estimated mean | 26.86 | 24.73 | 28.80 | 46.64 | 47.47 | 46.08 | ||
8 weeks, estimated mean (% change from pre-enrollment time point) | 18.71 (–30.3) | 17.61 (–28.8) | 19.71 (–31.6) | 28.68 (–38.5) | 33.84 (–28.7) | 25.17 (–45.4) | ||
20 weeks, estimated mean (% change from pre-enrollment time point) | 16.49 (–38.6) | 15.52 (–37.2) | 17.37 (–39.6) | 23.67 (–49.3) | 24.78 (–47.8) | 22.91 (–50.3) | ||
Pre-enrollment time point, estimated mean | 40.83 | 40.92 | 40.75 | 37.63 | 37.16 | 38.02 | ||
8 weeks, estimated mean (% change from pre-enrollment time point) | 42.22 (3.4) | 41.86 (2.3) | 42.55 (4.4) | 39.78 (5.7) | 38.49 (3.6) | 40.86 (7.5) | ||
20 weeks, estimated mean (% change from pre-enrollment time point) | 43.35 (6.2) | 43.28 (5.8) | 43.41 (6.5) | 41.11 (9.3) | 40.34 (8.6) | 41.76 (9.8) | ||
Pre-enrollment time point, estimated mean | 3.28 | 3.33 | 3.24 | 2.92 | 2.96 | 2.88 | ||
8 weeks, estimated mean (% change from pre-enrollment time point) | 3.51 (6.8) | 3.47 (4.0) | 3.54 (9.3) | 3.29 (12.9) | 3.32 (12.3) | 3.27 (13.5) | ||
20 weeks, estimated mean (% change from pre-enrollment time point) | 3.48 (5.9) | 3.55 (6.5) | 3.41 (5.3) | 3.26 (11.8) | 3.33 (12.5) | 3.20 (11.0) |
b PHQ-9: Patient Health Questionnaire–9.
c Entire sample—both conditions: n=107, ICBT-only condition: n=51, and ICBT plus peer support forum: n=56; clinical subsamples—both conditions: n=53, ICBT-only condition: n=26, and ICBT plus peer support forum: n=27.
d GAD-7: Generalized Anxiety Disorder–7.
e Entire sample—both conditions: n=107, ICBT-only condition: n=51, and ICBT plus peer support forum: n=56; clinical subsamples—both conditions: n=39, ICBT-only condition: n=19, and ICBT plus peer support forum: n=20.
f PCL-5: PTSD Checklist for DSM-5.
g Entire sample—both conditions: n=107, ICBT-only condition: n=51, and ICBT plus peer support forum: n=56; clinical subsamples—both conditions: n=42, ICBT-only condition: n=17, and ICBT plus peer support forum: n=25.
h FS: Flourishing Scale.
i Entire sample—both conditions: n=107, ICBT-only condition: n=51, and ICBT plus peer support forum: n=56; clinical subsamples—both conditions: n=81, ICBT-only condition: n=37, and ICBT plus peer support forum: n=44.
j BRS: Brief Resilience Scale.
k Entire sample—both conditions: n=107, ICBT-only condition: n=51, and ICBT plus peer support forum: n=56; clinical subsamples—both conditions: n=78, ICBT-only condition: n=37, and ICBT plus peer support forum: n=41.
Variables | Entire sample | Clinical subsamples | ||||||
test ( ) | value | Cohen | test ( ) | value | Cohen | |||
Pre-enrollment time point to 8 weeks after beginning treatment | –4.44 (158.78) | <.001 | –0.70 | –6.80 (76.52) | <.001 | –1.55 | ||
Pre-enrollment time point to 20 weeks after beginning treatment | –6.55 (160.38) | <.001 | –1.03 | –8.39 (78.87) | <.001 | –1.89 | ||
8-20 weeks after beginning treatment | –2.20 (156.57) | .03 | –0.35 | –2.11 (77.13) | .04 | –0.48 | ||
Pre-enrollment time point to 8 weeks after beginning treatment | –4.18 (158.10) | <.001 | –0.66 | –6.67 (54.53) | <.001 | –1.81 | ||
Pre-enrollment time point to 20 weeks after beginning treatment | –5.77 (159.88) | <.001 | –0.91 | –6.56 (56.78) | <.001 | –1.74 | ||
8-20 weeks after beginning treatment | –1.71 (155.65) | .09 | –0.27 | –0.52 (54.08) | .61 | –0.14 | ||
Pre-enrollment time point to 8 weeks after beginning treatment | –5.67 (151.91) | <.001 | –0.92 | –8.39 (57.98) | <.001 | –2.20 | ||
Pre-enrollment time point to 20 weeks after beginning treatment | –6.88 (152.70) | <.001 | –1.11 | –10.58 (58.75) | <.001 | –2.76 | ||
8-20 weeks after beginning treatment | –1.42 (149.50) | .16 | –0.23 | –2.51 (56.12) | .02 | –0.67 | ||
Pre-enrollment time point to 8 weeks after beginning treatment | 2.10 (159.08) | .04 | 0.33 | 2.61 (118.39) | .01 | 0.48 | ||
Pre-enrollment time point to 20 weeks after beginning treatment | 3.67 (159.97) | <.001 | 0.58 | 4.11 (119.64) | <.001 | 0.75 | ||
8-20 weeks after beginning treatment | 1.60 (157.12) | .11 | 0.26 | 1.55 (117.03) | .12 | 0.29 | ||
Pre-enrollment time point to 8 weeks after beginning treatment | 3.00 (160.80) | .003 | 0.47 | 4.94 (115.02) | <.001 | 0.92 | ||
Pre-enrollment time point to 20 weeks after beginning treatment | 2.55 (162.06) | .01 | 0.40 | 4.23 (116.22) | <.001 | 0.78 | ||
8-20 weeks after beginning treatment | –0.29 (158.65) | .77 | –0.05 | –0.39 (112.77) | .70 | –0.07 |
a PHQ-9: Patient Health Questionnaire–9.
b Entire sample: n=107; clinical subsamples: n=53.
c GAD-7: Generalized Anxiety Disorder–7.
d Entire sample: n=107; clinical subsamples: n=39.
e PCL-5: PTSD Checklist for DSM-5.
f Entire sample: n=107; clinical subsamples: n=42.
g FS: Flourishing Scale.
h Entire sample: n=107; clinical subsamples: n=81.
i BRS: Brief Resilience Scale.
j Entire sample: n=107; clinical subsamples: n=78.
Program Use
There was no statistically significant difference between groups with respect to the number of lessons participants accessed by 8 weeks (t 105 =–0.28; P= .78; Cohen d =–0.05) or 20 weeks (t 105 =0.82; P= .42; Cohen d =0.16). Collapsing across groups, a sizeable minority of participants accessed all 5 lessons of the Self-Guided PSP Wellbeing Course by 8 weeks (30/107, 28%) or 20 weeks (46/107, 43%). Nearly half (48/107, 44.9%) accessed 4 of 5 lessons by 8 weeks, whereas more than half (59/107, 55.1%) accessed 4 of 5 lessons by 20 weeks. Participants accessed an average of 3.33 (SD 5.00) additional resources. Responses to the Program Use Questionnaire collapsed across groups and averaged across time points (ie, 2, 4, 6, and 8 weeks) showed that participants most commonly reported putting “some effort” into the course (39%), followed by “a little effort” (30.9%), “no effort” (17.5%), and “a lot of effort” (12.5%), with no participants reporting “a great deal of effort” at any time point.
Treatment Satisfaction
The Treatment Satisfaction Questionnaire and SRS were completed by 68% (38/56) of the participants in the ICBT plus peer support forum condition and 88% (45/51) of the participants in the ICBT-only condition. Two-tailed independent-sample t tests and chi-square tests showed no statistically significant differences between groups with respect to any treatment satisfaction variables ( P ≥.47 in all cases). Accordingly, we present the results collapsed across groups in Table 4 .
We qualitatively analyzed responses to open-ended questions from 61.7% (66/107) of the participants, which we organized into 3 main themes: positive feedback, negative or constructive feedback, and comments about personal circumstances or preferences that do not reflect the perceived helpfulness of the Self-Guided PSP Wellbeing Course . The results are shown in Table 5 .
Variables | Values | |
Yes | 79 (96) | |
No | 3 (4) | |
Yes | 78 (94) | |
No | 5 (6) | |
Very dissatisfied (0), n (%) | 0 (0) | |
Dissatisfied (1), n (%) | 0 (0) | |
Neutral (2), n (%) | 31 (37) | |
Satisfied (3), n (%) | 45 (54) | |
Very satisfied (4), n (%) | 7 (8) | |
Values, mean (SD) | 2.71 (0.62) | |
Greatly reduced (0), n (%) | 3 (4) | |
Reduced (1), n (%) | 3 (4) | |
No change (2), n (%) | 21 (26) | |
Increased (3), n (%) | 49 (60) | |
Greatly increased (4), n (%) | 6 (7) | |
Values, mean (SD) | 2.63 (0.82) | |
Strongly disagree | 2 (2) | |
Disagree | 14 (17) | |
Neutral | 32 (39) | |
Agree | 27 (33) | |
Strongly agree | 7 (9) | |
Strongly disagree | 3 (4) | |
Disagree | 19 (23) | |
Neutral | 32 (39) | |
Agree | 20 (24) | |
Strongly agree | 8 (10) | |
, mean (SD) | ||
Bond (n=83) | 4.55 (1.13) | |
Goals (n=82) | 4.67 (1.01) | |
Tasks (n=82) | 4.37 (1.50) | |
Overall (n=82) | 4.55 (1.29) |
a SRS: Session Rating Scale.
Theme, subtheme, and category | Example quote | Frequency, n (%) | ||
Positive feedback on stories or case examples | “I liked the stories cause it helped me relate and see other people are having these experiences.” [Participant 1801] | 18 (27) | ||
Positive feedback on DIY guides | “DIY Guides are very informative and easy to understand.” [Participant 1256] | 17 (26) | ||
Positive feedback on additional resources | “I liked the resource library to be accessed for follow up and reminders.” [Participant 1757] | 13 (20) | ||
Positive feedback on course content (eg, thorough, understandable, and relatable) | “It goes into explanations that in person therapy doesn’t seem to have time for, or, that in person therapists don’t think to cover.” [Participant 1392] | 8 (12) | ||
Positive feedback on lessons | “Lessons were straight forward and easy to comprehend.” [Participant 1583] | 5 (8) | ||
Positive feedback on tools and skills taught in the course | “Gave me a framework to understand what has been affecting me and how to work on it productively. I have taken my time, more than intended by the course I think, to practice the skills.” [Participant 1175] | 6 (9) | ||
Course acted as a helpful reminder of previously learned skills and information | “Good refresher and reminder of important concepts.” [Participant 1342] | 4 (6) | ||
Liked that the course was self-guided, self-paced, or accessible at any time and location | “[Liked] being able to work on the course on my own timeline, when I was in the right headspace. It didn’t feel forced.” [Participant 1091] | 12 (18) | ||
Liked the format or structure of the course or the presentation or delivery of information | “I liked how the course was structured.” [Participant 1648] | 10 (15) | ||
Liked being able to download or print course materials or review them again in the future | “It is nice to have the resources to go back to in the future.” [Participant 1648] | 5 (8) | ||
Liked the reminder emails | “[Liked] reminders to keep at it.” [Participant 1225] | 3 (5) | ||
General statement of liking the course | “[Liked] honestly, all of it.” [Participant 1092] | 2 (3) | ||
No positive feedback provided | — | 2 (3) | ||
Disliked the stories, did not find them helpful, or provided feedback on them | “I didn’t find the stories particularly helpful.” [Participant 1154] | 5 (8) | ||
Course was too basic or recommendation for a second course with more tools | “I thought it would be longer and more in depth.” [Participant 1742] | 3 (5) | ||
Some content seemed redundant or unnecessary | “I found the lessons and DIY guides a bit repetitive (they covered a lot of the same material).” [Participant 1173] | 2 (3) | ||
Other suggestions for improving clinical content | “I was approaching this as a preventative course as opposed to a treatment course so I found that the examples were not something I identified with. It would be wonderful if there was a separate course for individuals looking to build skills to help prevent a slide into negative mental health.” [Participant 1258] | 3 (5) | ||
Difficulty or dislike concerning the current use of timelines and reminders to motivate completion | “I needed more time and felt somewhat anxious when the reminders were coming about a new section and I was behind.” [Participant 1503] | 7 (11) | ||
Would prefer if the course included therapist support | “I wished I also had the therapist to help keep me on track and discuss some of my thoughts and feelings that came up while taking the course.” [Participant 1801] | 5 (8) | ||
Disliked amount of reading or suggested more video content | “[Disliked] a lot of reading. Hard to stay focused.” [Participant 1546] | 3 (5) | ||
Course was not mobile friendly | “The slides were difficult to read in a phone. Sitting at a computer isn’t always an option for privacy.” [Participant 1181] | 1 (2) | ||
No dislikes identified or constructive feedback provided | “There is nothing I didn’t like.” [Participant 1242] | 29 (44) | ||
Limited time, energy, or capacity to work on the course or unexpected life circumstances posing a barrier to progression in the course | “Nothing you can do but life threw me a curve the past couple weeks, very sick kitten so that was my immediate concern and this fell to the wayside.” [Participant 1816] | 6 (9) | ||
Hard time with web-based courses in general, preference for in-person courses or would benefit more from in-person courses | “I would benefit more from in-person treatment, but am reluctant to participate.” [Participant 1225] | 3 (5) |
a DIY: do-it-yourself.
b Not applicable.
Online Discussion Forum Use and Satisfaction
Only 9% (5/56) of the participants in the ICBT plus peer support forum condition posted in the forum, creating 9 posts in total. The moderator (author HCM) created an additional 16 posts in an effort to spark discussion. The Treatment Satisfaction Questionnaire was completed by 38 participants in the ICBT plus peer support forum condition, 14 (37%) of whom reported that they did not use the forum. Of the remaining 24 participants, 1 (4%) reported feeling “very satisfied” with the forum overall, 11 (46%) reported feeling “satisfied,” 8 (33%) reported feeling “neutral,” 4 (17%) reported feeling “dissatisfied,” and none reported feeling “very dissatisfied.” Among the 38 participants in the ICBT plus peer support forum who completed the Treatment Satisfaction Questionnaire were 15 (39%) who reported reading between “a few” posts and “all or nearly all” posts, including participants who reported that reading others’ posts was “highly beneficial” (n=2, 13%), “beneficial” (n=3, 20%), “somewhat beneficial” (n=6, 40%), and “not beneficial at all” (n=4, 27%).
We received meaningful, analyzable feedback on the peer support forum from 52% (29/56) of the participants, identifying 17 categories of feedback, which we grouped into 3 general themes: positive feedback, constructive or negative feedback, and other personal reactions to the forum. The results of this content analysis are shown in Table 6 .
Theme, subtheme, and category | Example quote | Frequency, n (%) | |||
Liked that the forum was supportive, open, or free of judgment | “Judgement-free, supportive space to use when/if/how helpful.” [Participant 1217] | 2 (7) | |||
Liked reading others’ comments or seeing a variety of perspectives | “[Liked] variety of viewpoints.” [Participant 1217] | 2 (7) | |||
Liked not feeling alone | “It’s nice to know you’re not alone.” [Participant 1816] | 2 (7) | |||
Liked that the forum was an option | “[Liked] that it was an option.” [Participant 1978] | 1 (3) | |||
Did not like anything about the forum | “I did not [like the forum]. Possibly I didn’t connect properly?” [Participant 1721] | 2 (7) | |||
Dislike, discomfort, or difficulty opening up to or being vulnerable with others | “[Did not post because] police culture does not encourage sharing or vulnerability with mental health. Peer forums are not a tool we are comfortable with. Especially with the association of privacy and information release in our jobs.” [Participant 1181] | 8 (28) | |||
Disliked the low level of forum activity or did not post due to low activity level | “[Disliked that] it was not an active forum and often nothing had been posted.” [Participant 1978] | 7 (24) | |||
Unaware of forum or comment that more prompts would result in greater forum use | “[Did not post because the forum] wasn’t emphasized enough as an available tool or resource during the course. I also did not know it was available to me.” [Participant 1095] | 4 (14) | |||
Would prefer a scheduled live chat to asynchronous posts | “Wished it was more of a real time chat.” [Participant 1801] | 2 (7) | |||
General statement of dislike for or disinterest in the forum | “I did not like it.” [Participant 1130] | 2 (7) | |||
Too much involvement from the moderator | “[Disliked that the forum was]...very monitored?” [Participant 1721] | 1 (3) | |||
Disliked nothing about the forum | “[Disliked] nothing.” [Participant 1241] | 1 (3) | |||
Did not post because of other demands or not enough time | “[Did not post because] work and life demands paused my participation in the program.” [Participant 1584] | 4 (14) | |||
Participant did not feel that they had anything of value to add to forum | [Did not post because] “I felt I didn’t have anything to add of value.” [Participant 1816] | 3 (10) | |||
Comment on how it felt to post on the forum | “[It felt] very difficult, vulnerable to do, felt unburdened/heard after posting.” [Participant 1217] | 2 (7) | |||
Misconception that participants cannot respond to each other | “[Disliked that the forum] seemed like a question and answer type without being able to respond to each other.” [Participant 1721] | 1 (3) | |||
Did not feel a need to post because other aspects of the course were sufficient | “[Did not post because] I am still stuck on capturing my thoughts and found that the FAQ suffices.” [Participant 1168] | 1 (3) |
Principal Findings
ICBT is an effective mental health treatment [ 1 ], but clients demonstrate somewhat less favorable clinical outcomes [ 5 - 12 ] and engagement [ 13 - 15 ] when it is offered in a purely self-guided format. Persuasive design principles represent a possible means of improving engagement and outcomes in DMHIs [ 5 , 20 ], and preliminary evidence supports the use of social support principles of persuasive design implemented via online discussion forums [ 3 , 23 - 29 ], but there is a dearth of experimental research directly evaluating the impact of forums in ICBT or other DMHIs. Research has also shown that Canadian PSP benefit considerably from tailored, guided ICBT [ 34 - 36 ], but previous research has not evaluated self-guided ICBT among Canadian PSP. We conducted a randomized trial to assess the impact of adding an online discussion forum to self-guided ICBT and evaluate outcomes of tailored, self-guided ICBT among Canadian PSP.
Participants showed large improvements in symptoms of depression, anxiety, and posttraumatic stress, which supported and surpassed our hypothesis of at least small to moderate reductions in symptoms. Most meta-analyses of self-guided DMHIs have not reported pretest-posttest effect sizes, but our results for changes in depression over time compare favorably to the pretest-posttest effect size of d =0.78 reported in one meta-analysis of self-guided DMHIs for depression [ 87 ]. Changes in flourishing and resilience were more modest, potentially because the Self-Guided PSP Wellbeing Course was designed to reduce symptoms of mental disorders but not explicitly designed to improve flourishing or resilience. Nevertheless, the finding of improvements in flourishing and resilience makes an important contribution to the research literature as research on the effects of ICBT on these constructs is scarce.
The symptom change and treatment satisfaction demonstrated in this study were roughly comparable to those observed in research on the guided version of the PSP Wellbeing Course , likely because the 2 courses included practically identical treatment materials. However, engagement with the guided version was markedly better, with only 5.7% of enrolled PSP failing to access or withdrawing from the intervention (compared to 46/153, 30% in this study), 76.1% of participants accessing at least 4 of the 5 lessons of the course within 8 weeks (compared to 48/107, 44.9% in this study), and 57.3% completing the course within 8 weeks (compared to 30/107, 28% in this study) [ 36 ]. These findings suggest that therapists play a pivotal role in both initiating and sustaining Canadian PSP’s engagement in ICBT. This conclusion aligns with those of previous research showing that PSP very frequently cite therapist guidance as a liked aspect of ICBT [ 88 ] and with a broader research literature showing that engagement tends to be lower in self-guided than in guided DMHIs [ 13 - 15 ]. Nevertheless, engagement with the Self-Guided PSP Wellbeing Course in this study appears to compare favorably to that of other research on self-guided DMHIs. In a systematic review, Kelders et al [ 20 ] found, on average, a 54.2% rate of “intended use” (ie, some engagement but not necessarily completion) of internet interventions for mental health, including both guided and self-guided interventions. Another systematic review found real-world completion rates ranging from 0.5% to 28.6% for self-guided DMHIs [ 14 ]. Engagement in the present study may have been enhanced by the structure provided by the randomized trial design as this kind of study design was found to predict greater engagement in the review by Kelders et al [ 20 ]. Interestingly, only a minority of participants in the present study indicated that they would have preferred to receive therapist guidance via email or phone while taking the course.
The results failed to support our hypothesis that participants assigned to the ICBT plus peer support forum condition would demonstrate greater engagement and treatment outcomes. Given participants’ limited engagement with the peer support forum, this was unsurprising. The proportion of participants who posted in the forum (5/56, 9%) was far lower than proportions of 53% [ 26 ] and 50.6% [ 28 ] reported in previous studies of forums in DMHIs. Similarly, the mean number of posts per participant (0.16) was far lower than the means of 13.1 [ 89 ], 4.5 [ 89 ], 2.2 [ 29 ], and 1.86 [ 28 ] reported in previous studies. We are aware of only one previous study in which a lower proportion (ie, 7%) of participants posted in a forum accompanying a DMHI [ 90 ]. Despite low engagement with the peer support forum, some participants reported feeling satisfied with it and indicated that reading posts was beneficial, with qualitative feedback suggesting that some participants felt that the forum was supportive and helped them feel that they were not alone.
There are several possible reasons for the low engagement with the forum in this study. First, qualitative feedback suggested that many participants felt uncomfortable opening up to others and showing vulnerability, with one participant explicitly attributing this to “police culture,” suggesting that forums may be a poor fit for many PSP. Second, the fact that the Self-Guided PSP Wellbeing Course was transdiagnostic, with different participants experiencing different symptoms, may have led participants to feel that they did not have much in common with other forum users and, therefore, may also have detracted from their comfort in sharing their experiences. Third, forums may be particularly helpful as an adjunct to treatment for certain conditions; indeed, much of the past research supporting the use of forums in ICBT has been conducted within the context of ICBT for social anxiety [ 3 , 23 , 27 , 28 ]. Fourth, the PSP who self-selected into this study may have been particularly interested in independently accessing a self-guided treatment, whereas PSP who were interested in sharing their experiences with others may have opted for other mental health care options (including PSPNET’s therapist-guided ICBT for PSP in provinces where it was available). Finally, there was likely room for improvement with respect to the structure and implementation of the forum and our efforts to encourage participants to use it.
There was only one statistically significant difference observed between conditions: a greater proportion of participants completed questionnaires at 8 weeks in the ICBT-only condition. It remains unclear why this occurred. It could be a spurious finding. It could also be that participants in the ICBT plus peer support forum condition inferred from the minimal forum engagement that engagement with the study as a whole was low and were less likely to complete questionnaires due to the phenomenon of social normative influence [ 91 ].
Strengths, Limitations, and Future Research
This study benefitted from a mixed methods approach, allowing for both a quantitative evaluation of treatment outcomes and a qualitative exploration of participants’ experiences. Another strength of this study was its ecological validity as we evaluated the Self-Guided PSP Wellbeing Course and the peer support forum under the conditions in which they were designed to be implemented. This study also had important limitations. We did not include a control condition with which to compare outcomes of the course, and our inclusion of multiple outcome measures in separate analyses increased our familywise error rate. We expect that every discussion forum is unique and its social dynamics are unpredictable; therefore, a key limitation of this study is that it is, in a sense, a case study of a single forum with results that may not generalize well to other forums. This study was also sufficiently powered to detect only moderate differences between conditions, and due to an unexpectedly high rate of withdrawal from the study or failure to begin the intervention after we had ceased recruitment, we ultimately included 3 fewer participants in our analyses than originally planned. Finally, because we did not exclude participants with minimal or mild pre-enrollment symptoms from this research, floor effects are likely present in quantitative analyses conducted among our entire sample.
Future research can expand on this study and address the limitations noted previously in several ways. Although the peer support forum in this study had no demonstrable effect on treatment outcomes, previous research has shown excellent outcomes for online discussion forums [ 3 , 23 - 29 ], highlighting a need for further experimental research to evaluate the impact of forums on treatment outcomes in self-guided DMHIs. We are aware of a large factorial randomized trial assessing, among other things, the impact of an online discussion forum on treatment outcomes in ICBT, but the results of this trial are not yet available [ 92 ]. It would also be helpful for future research to identify common characteristics of forums that function well and those that do not, further explore DMHI users’ perspectives on forums, and identify strategies for improving engagement with forums drawing on the persuasive system design framework and other work. With respect to outcomes of self-guided ICBT tailored for PSP, future research could compare treatment outcomes against a control condition, assess longer-term outcomes, and assess additional outcomes that we did not assess.
Conclusions
ICBT has shown excellent outcomes for treating a range of psychological concerns among PSP [ 34 - 36 ] and the general population [ 1 ]. Self-guided ICBT is more scalable but shows poorer engagement and outcomes than therapist-guided ICBT [ 5 - 15 ]. There is emerging evidence suggesting that persuasive design may help improve engagement and outcomes in ICBT [ 5 , 19 - 21 ], but further research is needed. We conducted a randomized trial, finding that transdiagnostic self-guided ICBT tailored specifically for PSP showed good outcomes, but PSP randomly assigned to receive access to a built-in online discussion forum showed limited engagement with it and no evidence of benefitting from it. Our findings support the continued implementation of self-guided ICBT. Our findings contrast with those of previous research on discussion forums in DMHIs, which have generally shown promising engagement and outcomes [ 3 , 23 - 29 , 89 ], highlighting a need for more research to clarify the circumstances under which forums may help improve engagement and outcomes in DMHIs. More broadly, as DMHIs become increasingly popular, there is a great need for more research identifying possible strategies to make them more engaging and effective, including—but not limited to—further research evaluating the impact of specific persuasive design principles.
Acknowledgments
The authors would like to thank Dr Janine Beahm for her feedback on their qualitative analyses and Dr Donald Sharpe for his recommendations regarding their quantitative analyses. The authors would like to thank all past and current members of the PSPNET team and all public safety personnel who participated in this research for making it possible. Particular thanks are due to Julia Gregory for her work as a research assistant in carrying out this study. The authors would like to thank Drs Nick Titov and Blake Dear for sharing treatment materials used to develop the Self-Guided PSP Wellbeing Course . This research was supported by funding from the Canadian Institutes of Health Research and Public Safety Canada; neither funder had any involvement in carrying out this research. Finally, acknowledgments are due to the Public Safety Canada Steering Committee, the Canadian Institute for Public Safety Research and Treatment, the Online Therapy Unit, and Information Services at the University of Regina for supporting this research.
Data Availability
The data sets generated and analyzed during this study are not publicly available due our commitment to our participants to securely store their data and refrain from sharing them with anyone outside of our research team.
Conflicts of Interest
None declared.
Sample size planning.
Covariate analyses.
Observed descriptive statistics on questionnaire scores.
- Andersson G, Carlbring P, Titov N, Lindefors N. Internet interventions for adults with anxiety and mood disorders: a narrative umbrella review of recent meta-analyses. Can J Psychiatry. Jul 16, 2019;64(7):465-470. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Christensen H, Hickie IB. E-mental health: a new era in delivery of mental health services. Med J Aust. Jun 07, 2010;192(S11):S2-S3. [ CrossRef ] [ Medline ]
- Furmark T, Carlbring P, Hedman E, Sonnenstein A, Clevberger P, Bohman B, et al. Guided and unguided self-help for social anxiety disorder: randomised controlled trial. Br J Psychiatry. Nov 2009;195(5):440-447. [ CrossRef ] [ Medline ]
- Richards D, Enrique A, Palacios J, Duffy D. Internet-delivered cognitive behaviour therapy. In: Şenormancı Ö, Şenormancı G, editors. Cognitive Behavioral Therapy and Clinical Applications. London, UK. IntechOpen; 2018.
- McCall HC, Hadjistavropoulos HD, Sundström CR. Exploring the role of persuasive design in unguided internet-delivered cognitive behavioral therapy for depression and anxiety among adults: systematic review, meta-analysis, and meta-regression. J Med Internet Res. Apr 29, 2021;23(4):e26939. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Karyotaki E, Riper H, Twisk J, Hoogendoorn A, Kleiboer A, Mira A, et al. Efficacy of self-guided internet-based cognitive behavioral therapy in the treatment of depressive symptoms: a meta-analysis of individual participant data. JAMA Psychiatry. Apr 01, 2017;74(4):351-359. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Andersson G, Cuijpers P. Internet-based and other computerized psychological treatments for adult depression: a meta-analysis. Cogn Behav Ther. 2009;38(4):196-205. [ CrossRef ] [ Medline ]
- Wright JH, Owen JJ, Richards D, Eells TD, Richardson T, Brown GK, et al. Computer-assisted cognitive-behavior therapy for depression: a systematic review and meta-analysis. J Clin Psychiatry. Mar 19, 2019;80(2):18r12188. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Spek V, Cuijpers P, Nyklícek I, Riper H, Keyzer J, Pop V. Internet-based cognitive behaviour therapy for symptoms of depression and anxiety: a meta-analysis. Psychol Med. Mar 2007;37(3):319-328. [ CrossRef ] [ Medline ]
- Krieger T, Bur OT, Weber L, Wolf M, Berger T, Watzke B, et al. Human contact in internet-based interventions for depression: a pre-registered replication and meta-analysis of randomized trials. Internet Interv. Apr 2023;32:100617. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Baumeister H, Reichler L, Munzinger M, Lin J. The impact of guidance on internet-based mental health interventions — a systematic review. Internet Interv. Oct 2014;1(4):205-215. [ CrossRef ]
- Karyotaki E, Efthimiou O, Miguel C, Bermpohl FM, Furukawa TA, Cuijpers P, Individual Patient Data Meta-Analyses for Depression (IPDMA-DE) Collaboration, et al. Internet-based cognitive behavioral therapy for depression: a systematic review and individual patient data network meta-analysis. JAMA Psychiatry. Apr 01, 2021;78(4):361-371. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Andersson G, Carlbring P, Berger T, Almlöv J, Cuijpers P. What makes internet therapy work? Cogn Behav Ther. 2009;38 Suppl 1:55-60. [ CrossRef ] [ Medline ]
- Fleming TM, Bavin L, Lucassen M, Stasiak K, Hopkins S, Merry S. Beyond the trial: systematic review of real-world uptake and engagement with digital self-help interventions for depression, low mood, or anxiety. J Med Internet Res. Jun 06, 2018;20(6):e199. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Gan DZ, McGillivray L, Larsen ME, Christensen H, Torok M. Technology-supported strategies for promoting user engagement with digital mental health interventions: a systematic review. Digit Health. Jun 01, 2022;8:205520762210982. [ CrossRef ]
- Andersson G, Titov N. Advantages and limitations of internet-based interventions for common mental disorders. World Psychiatry. Feb 2014;13(1):4-11. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Gerhards SA, de Graaf LE, Jacobs LE, Severens JL, Huibers MJ, Arntz A, et al. Economic evaluation of online computerised cognitive-behavioural therapy without support for depression in primary care: randomised trial. Br J Psychiatry. Apr 2010;196(4):310-318. [ CrossRef ] [ Medline ]
- Lorenzo-Luaces L, Johns E, Keefe JR. The generalizability of randomized controlled trials of self-guided internet-based cognitive behavioral therapy for depressive symptoms: systematic review and meta-regression analysis. J Med Internet Res. Nov 09, 2018;20(11):e10113. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Fleming TM, de Beurs D, Khazaal Y, Gaggioli A, Riva G, Botella C, et al. Maximizing the impact of e-therapy and serious gaming: time for a paradigm shift. Front Psychiatry. 2016;7:65. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Kelders SM, Kok RN, Ossebaard HC, van Gemert-Pijnen JE. Persuasive system design does matter: a systematic review of adherence to web-based interventions. J Med Internet Res. Nov 14, 2012;14(6):e152. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Ludden GD, van Rompay TJ, Kelders SM, van Gemert-Pijnen JE. How to increase reach and adherence of web-based interventions: a design research viewpoint. J Med Internet Res. Jul 10, 2015;17(7):e172. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Oinas-Kukkonen H, Harjumaa M. Persuasive systems design: key issues, process model, and system features. Commun Assoc Inf Syst. 2009;24:485-501. [ CrossRef ]
- Andersson G, Carlbring P, Holmström A, Sparthan E, Furmark T, Nilsson-Ihrfelt E, et al. Internet-based self-help with therapist feedback and in vivo group exposure for social phobia: a randomized controlled trial. J Consult Clin Psychol. Aug 2006;74(4):677-686. [ CrossRef ] [ Medline ]
- Boettcher J, Aström V, Påhlsson D, Schenström O, Andersson G, Carlbring P. Internet-based mindfulness treatment for anxiety disorders: a randomized controlled trial. Behav Ther. Mar 2014;45(2):241-253. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Johansson P, Westas M, Andersson G, Alehagen U, Broström A, Jaarsma T, et al. An internet-based cognitive behavioral therapy program adapted to patients with cardiovascular disease and depression: randomized controlled trial. JMIR Ment Health. Oct 03, 2019;6(10):e14648. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Hesser H, Gustafsson T, Lundén C, Henrikson O, Fattahi K, Johnsson E, et al. A randomized controlled trial of internet-delivered cognitive behavior therapy and acceptance and commitment therapy in the treatment of tinnitus. J Consult Clin Psychol. Aug 2012;80(4):649-661. [ CrossRef ] [ Medline ]
- Titov N, Andrews G, Schwencke G, Solley K, Johnston L, Robinson E. An RCT comparing effect of two types of support on severity of symptoms for people completing internet-based cognitive behaviour therapy for social phobia. Aust N Z J Psychiatry. Jan 01, 2009;43(10):920-926. [ CrossRef ]
- Berger T, Caspar F, Richardson R, Kneubühler B, Sutter D, Andersson G. Internet-based treatment of social phobia: a randomized controlled trial comparing unguided with two types of guided self-help. Behav Res Ther. Mar 2011;49(3):158-169. [ CrossRef ] [ Medline ]
- Carolan S, Harris PR, Greenwood K, Cavanagh K. Increasing engagement with an occupational digital stress management program through the use of an online facilitated discussion group: results of a pilot randomised controlled trial. Internet Interv. Dec 2017;10:1-11. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Carleton RN, Afifi TO, Taillieu T, Turner S, Krakauer R, Anderson GS, et al. Exposures to potentially traumatic events among public safety personnel in Canada. Can J Behav Sci. Jan 2019;51(1):37-52. [ CrossRef ]
- Carleton RN, Afifi TO, Turner S, Taillieu T, Duranceau S, LeBouthillier DM, et al. Mental disorder symptoms among public safety personnel in Canada. Can J Psychiatry. Jan 28, 2018;63(1):54-64. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Ricciardelli R, Carleton RN, Mooney T, Cramm H. "Playing the system": structural factors potentiating mental health stigma, challenging awareness, and creating barriers to care for Canadian public safety personnel. Health (London). May 16, 2020;24(3):259-278. [ CrossRef ] [ Medline ]
- McCall HC, Beahm JD, Fournier AK, Burnett JL, Carleton RN, Hadjistavropoulos HD. Stakeholder perspectives on internet-delivered cognitive behavioural therapy for public safety personnel: a qualitative analysis. Can J Behav Sci. Jul 2021;53(3):232-242. [ CrossRef ]
- Hadjistavropoulos HD, McCall HC, Thiessen DL, Huang Z, Carleton RN, Dear BF, et al. Initial outcomes of transdiagnostic internet-delivered cognitive behavioral therapy tailored to public safety personnel: longitudinal observational study. J Med Internet Res. May 05, 2021;23(5):e27610. [ FREE Full text ] [ CrossRef ] [ Medline ]
- McCall H, Dear BF, Landry C, Beahm JD, Gregory J, Titov N, et al. Internet-delivered cognitive behavioural therapy for symptoms of PTSD among public safety personnel: initial outcomes of an open cohort preference trial of transdiagnostic and disorder-specific therapy. Internet Interv. Sep 2023;33:100656. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Hadjistavropoulos HD, McCall HC, Dear BF, Beahm JD, Carleton RN, Titov N. Outcomes of transdiagnostic internet-delivered cognitive behavioural therapy tailored to public safety personnel: a longitudinal observational study. J Anxiety Disord. Jun 2024;104:102861. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Kang M, Ragan BG, Park JH. Issues in outcomes research: an overview of randomization techniques for clinical trials. J Athl Train. 2008;43(2):215-221. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Sheehan DV. The Sheehan disability scales: the anxiety disease and how to overcome it. Mapi Research Trust. URL: https://eprovide.mapi-trust.org/instruments/sheehan-disability-scale [accessed 2024-04-29]
- Sharpe D, Cribbie RA. Analysis of treatment-control pre-post-follow-up design data. Quant Method Psychol. Feb 01, 2023;19(1):25-46. [ CrossRef ]
- Butcher NJ, Monsour A, Mew EJ, Chan AW, Moher D, Mayo-Wilson E, et al. Guidelines for reporting outcomes in trial reports: the CONSORT-outcomes 2022 extension. JAMA. Dec 13, 2022;328(22):2252-2264. [ CrossRef ] [ Medline ]
- Sunderland A, Findlay LC. Perceived need for mental health care in Canada: results from the 2012 Canadian Community Health Survey-Mental Health. Health Rep. Sep 2013;24(9):3-9. [ FREE Full text ] [ Medline ]
- Young C, Helis E, Williams D. Internet-delivered cognitive behavioural therapy for major depressive disorder and anxiety disorders: an environmental scan. Canadian Agency for Drugs and Technologies in Health. 2018. URL: https://www.cadth.ca/sites/default/files/pdf/ES0331_iCBT_for_Major_Depression_and_Anxiety.pdf [accessed 2024-04-29]
- Andersson G, Titov N, Dear BF, Rozental A, Carlbring P. Internet-delivered psychological treatments: from innovation to implementation. World Psychiatry. Feb 2019;18(1):20-28. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Donohue MC, Edland SD, Hu N. longpower: sample size calculations for longitudinal data. Cran R. URL: https://cran.r-project.org/web/packages/longpower/longpower.pdf [accessed 2024-04-29]
- Dear BF, Staples LG, Terides MD, Fogliati VJ, Sheehan J, Johnston L, et al. Transdiagnostic versus disorder-specific and clinician-guided versus self-guided internet-delivered treatment for social anxiety disorder and comorbid disorders: a randomized controlled trial. J Anxiety Disord. Aug 2016;42:30-44. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Berger T, Hämmerli K, Gubser N, Andersson G, Caspar F. Internet-based treatment of depression: a randomized controlled trial comparing guided with unguided self-help. Cogn Behav Ther. 2011;40(4):251-266. [ CrossRef ] [ Medline ]
- Andrews G, Basu A, Cuijpers P, Craske MG, McEvoy P, English CL, et al. Computer therapy for the anxiety and depression disorders is effective, acceptable and practical health care: an updated meta-analysis. J Anxiety Disord. Apr 2018;55:70-78. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Kroenke K, Spitzer RL, Williams JB. The PHQ-9: validity of a brief depression severity measure. J Gen Intern Med. Sep 2001;16(9):606-613. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Kroenke K, Spitzer RL, Williams JB, Löwe B. The patient health questionnaire somatic, anxiety, and depressive symptom scales: a systematic review. Gen Hosp Psychiatry. 2010;32(4):345-359. [ CrossRef ] [ Medline ]
- Manea L, Gilbody S, McMillan D. Optimal cut-off score for diagnosing depression with the Patient Health Questionnaire (PHQ-9): a meta-analysis. CMAJ. Feb 21, 2012;184(3):E191-E196. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Spitzer RL, Kroenke K, Williams JB, Löwe B. A brief measure for assessing generalized anxiety disorder: the GAD-7. Arch Intern Med. May 22, 2006;166(10):1092-1097. [ CrossRef ] [ Medline ]
- Blevins CA, Weathers FW, Davis MT, Witte TK, Domino JL. The posttraumatic stress disorder checklist for DSM-5 (PCL-5): development and initial psychometric evaluation. J Trauma Stress. Dec 2015;28(6):489-498. [ CrossRef ] [ Medline ]
- Bovin MJ, Marx BP, Weathers FW, Gallagher MW, Rodriguez P, Schnurr PP, et al. Psychometric properties of the PTSD checklist for diagnostic and statistical manual of mental disorders-fifth edition (PCL-5) in veterans. Psychol Assess. Nov 2016;28(11):1379-1391. [ CrossRef ] [ Medline ]
- Wortmann JH, Jordan AH, Weathers FW, Resick PA, Dondanville KA, Hall-Clark B, et al. Psychometric analysis of the PTSD Checklist-5 (PCL-5) among treatment-seeking military service members. Psychol Assess. Nov 2016;28(11):1392-1403. [ CrossRef ] [ Medline ]
- Leontjevas R, de Beek WO, Lataster J, Jacobs N. Resilience to affective disorders: a comparative validation of two resilience scales. J Affect Disord. Oct 2014;168:262-268. [ CrossRef ] [ Medline ]
- Smith BW, Dalen J, Wiggins K, Tooley E, Christopher P, Bernard J. The brief resilience scale: assessing the ability to bounce back. Int J Behav Med. 2008;15(3):194-200. [ CrossRef ] [ Medline ]
- Diener E, Wirtz D, Biswas-Diener R, Tov W, Kim-Prieto C, Choi DW, et al. New measures of well-being. In: Diener E, editor. Assessing Well-Being: The Collected Works of Ed Diener. Cham, Switzerland. Springer; 2009:247-266.
- Diener E, Wirtz D, Tov W, Kim-Prieto C, Choi D, Oishi S, et al. New well-being measures: short scales to assess flourishing and positive and negative feelings. Soc Indic Res. May 28, 2009;97(2):143-156. [ CrossRef ]
- Miller SD, Duncan BL, Johnson LD, Reynolds LR, Brown J. The session rating scale: preliminary psychometric properties of a “working” alliance measure. J Brif Ther. 2000;3(1):3-12. [ FREE Full text ]
- Campbell A, Hemsley S. Outcome rating scale and session rating scale in psychological practice: clinical utility of ultra-brief measures. Clin Psychol. Mar 11, 2009;13(1):1-9. [ CrossRef ]
- Duncan BL, Miller SD, Sparks JA, Claud DA, Reynolds LR, Brown J, et al. The session rating scale: preliminary psychometric properties of a “working” alliance measure. J Brif Ther. 2003;3(1):3-12. [ FREE Full text ]
- Cavanagh K, Herbeck Belnap B, Rothenberger SD, Abebe KZ, Rollman BL. My care manager, my computer therapy and me: the relationship triangle in computerized cognitive behavioural therapy. Internet Interv. Mar 2018;11:11-19. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Devilly GJ, Borkovec TD. Psychometric properties of the credibility/expectancy questionnaire. J Behav Ther Exp Psychiatry. Jun 2000;31(2):73-86. [ CrossRef ] [ Medline ]
- Saunders JB, Aasland OG, Babor TF, de la Fuente JR, Grant M. Development of the alcohol use disorders identification test (AUDIT): WHO collaborative project on early detection of persons with harmful alcohol consumption--II. Addiction. Jun 24, 1993;88(6):791-804. [ CrossRef ] [ Medline ]
- Berman AH, Bergman H, Palmstierna T, Schlyter F. Evaluation of the drug use disorders identification test (DUDIT) in criminal justice and detoxification settings and in a Swedish population sample. Eur Addict Res. 2005;11(1):22-31. [ CrossRef ] [ Medline ]
- McCall HC, Sison AP, Burnett JL, Beahm JD, Hadjistavropoulos HD. Exploring perceptions of internet-delivered cognitive behaviour therapy among public safety personnel: informing dissemination efforts. Int J Environ Res Public Health. Aug 19, 2020;17(17):6026. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Titov N, Dear BF, Staples LG, Bennett-Levy J, Klein B, Rapee RM, et al. MindSpot clinic: an accessible, efficient, and effective online treatment service for anxiety and depression. Psychiatr Serv. Oct 2015;66(10):1043-1050. [ CrossRef ] [ Medline ]
- Hadjistavropoulos HD, Peynenburg V, Thiessen DL, Nugent M, Karin E, Staples L, et al. Utilization, patient characteristics, and longitudinal improvements among patients from a provincially funded transdiagnostic internet-delivered cognitive behavioural therapy program: observational study of trends over 6 years. Can J Psychiatry. Mar 12, 2022;67(3):192-206. [ FREE Full text ] [ CrossRef ] [ Medline ]
- McCall HC, Hadjistavropoulos HD, Loutzenhiser L. Reconsidering the ethics of exclusion criteria in research on digital mental health interventions. Ethics Behav. Oct 31, 2019;31(3):171-180. [ CrossRef ]
- Harvey LA. Statistical testing for baseline differences between randomised groups is not meaningful. Spinal Cord. Oct 4, 2018;56(10):919. [ CrossRef ] [ Medline ]
- Gupta SK. Intention-to-treat concept: a review. Perspect Clin Res. Jul 2011;2(3):109-112. [ FREE Full text ] [ CrossRef ] [ Medline ]
- McNeish D. Small sample methods for multilevel modeling: a colloquial elucidation of REML and the Kenward-Roger correction. Multivariate Behav Res. Jul 17, 2017;52(5):661-670. [ CrossRef ] [ Medline ]
- Field AP. Discovering Statistics Using IBM SPSS Statistics. 5th edition. Thousand Oaks, CA. Sage Publications; 2018.
- Hair JF, Black WC, Babin BJ, Anderson RE. Multivariate Data Analysis. 7th edition. Harlow, UK. Pearson; 2014.
- Edmonds M, Hadjistavropoulos HD, Schneider LH, Dear BF, Titov N. Who benefits most from therapist-assisted internet-delivered cognitive behaviour therapy in clinical practice? predictors of symptom change and dropout. J Anxiety Disord. Mar 2018;54:24-32. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Beatty L, Binnion C. A systematic review of predictors of, and reasons for, adherence to online psychological interventions. Int J Behav Med. Dec 2016;23(6):776-794. [ CrossRef ] [ Medline ]
- Constantino MJ, Arnkoff DB, Glass CR, Ametrano RM, Smith JZ. Expectations. J Clin Psychol. Feb 2011;67(2):184-192. [ CrossRef ] [ Medline ]
- Thompson-Hollands J, Bentley KH, Gallagher MW, Boswell JF, Barlow DH. Credibility and outcome expectancy in the unified protocol: relationship to outcomes. J Exp Psychopathol. Mar 30, 2014;5(1):72-82. [ CrossRef ]
- Haller K, Becker P, Niemeyer H, Boettcher J. Who benefits from guided internet-based interventions? a systematic review of predictors and moderators of treatment outcome. Internet Interv. Sep 2023;33:100635. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Lambert MJ. Psychotherapy outcome research: implications for integrative and eclectical therapists. In: Norcross JC, Goldfried MR, editors. Handbook of Psychotherapy Integration. New York, NY. Basic Books; 1992:94-129.
- Elo S, Kyngäs H. The qualitative content analysis process. J Adv Nurs. Apr 2008;62(1):107-115. [ CrossRef ] [ Medline ]
- Berger R. Now I see it, now I don’t: researcher’s position and reflexivity in qualitative research. Qual Res. Jan 03, 2013;15(2):219-234. [ CrossRef ]
- The improving access to psychological therapies manual: appendices and helpful resources. National Collaborating Centre for Mental Health. 2019. URL: https://www.england.nhs.uk/wp-content/uploads/2018/06/iapt-manual-appendices-and-helpful-resources-v3.pdf [accessed 2020-12-15]
- Titov N, Dear BF, Staples LG, Bennett-Levy J, Klein B, Rapee RM, et al. The first 30 months of the mindspot clinic: evaluation of a national e-mental health service against project objectives. Aust N Z J Psychiatry. Dec 2017;51(12):1227-1239. [ CrossRef ] [ Medline ]
- Titov N, Dear BF, Nielssen O, Wootton B, Kayrouz R, Karin E, et al. User characteristics and outcomes from a national digital mental health service: an observational study of registrants of the Australian MindSpot Clinic. Lancet Digit Health. Nov 2020;2(11):e582-e593. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Byllesby BM, Dickstein BD, Chard KM. The probability of change versus dropout in veterans receiving cognitive processing therapy for posttraumatic stress disorder. Behav Res Ther. Dec 2019;123:103483. [ CrossRef ] [ Medline ]
- Richards D, Richardson T. Computer-based psychological treatments for depression: a systematic review and meta-analysis. Clin Psychol Rev. Jun 2012;32(4):329-342. [ CrossRef ] [ Medline ]
- Beahm JD, McCall HC, Carleton RN, Titov N, Dear B, Hadjistavropoulos HD. Insights into internet-delivered cognitive behavioural therapy for public safety personnel: exploration of client experiences during and after treatment. Internet Interv. Dec 2021;26:100481. [ FREE Full text ] [ CrossRef ] [ Medline ]
- Ljótsson B, Falk L, Vesterlund AW, Hedman E, Lindfors P, Rück C, et al. Internet-delivered exposure and mindfulness based therapy for irritable bowel syndrome--a randomized controlled trial. Behav Res Ther. Jun 2010;48(6):531-539. [ CrossRef ] [ Medline ]
- O'Mahen HA, Woodford J, McGinley J, Warren FC, Richards DA, Lynch TR, et al. Internet-based behavioral activation--treatment for postnatal depression (Netmums): a randomized controlled trial. J Affect Disord. Sep 25, 2013;150(3):814-822. [ CrossRef ] [ Medline ]
- Goldstein NJ, Cialdini RB, Griskevicius V. A room with a viewpoint: using social norms to motivate environmental conservation in hotels. J Consum Res. Oct 01, 2008;35(3):472-482. [ CrossRef ]
- Carlbring P, Lindqvist K, Mechler J, Philips B. Transdiagnostic self-help treatments for anxiety and/or depression: a full-factorial RCT investigating psychotherapeutic modalities, discussion boards and treatment length. In: Proceedings of the 11th Scientific Meeting on International Society for Research on Internet Interventions. 2022. Presented at: ISRII '22; September 18-21, 2022:1-19; Pittsburgh, PA. URL: https://www.diva-portal.org/smash/record.jsf?pid=diva2%3A1700061&dswid=-46
Abbreviations
Brief Resilience Scale |
Credibility/Expectancy Questionnaire |
Consolidated Standards of Reporting Trials |
digital mental health intervention |
Flourishing Scale |
Generalized Anxiety Disorder–7 |
internet-delivered cognitive behavioral therapy |
multilevel modeling |
PTSD Checklist for DSM-5 |
Patient Health Questionnaire–9 |
public safety personnel |
posttraumatic stress disorder |
Session Rating Scale |
Edited by A Mavragani; submitted 19.04.24; peer-reviewed by L Yang; comments to author 10.06.24; revised version received 26.06.24; accepted 22.07.24; published 14.08.24.
©Hugh C McCall, Heather D Hadjistavropoulos. Originally published in the Journal of Medical Internet Research (https://www.jmir.org), 14.08.2024.
This is an open-access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work, first published in the Journal of Medical Internet Research (ISSN 1438-8871), is properly cited. The complete bibliographic information, a link to the original publication on https://www.jmir.org/, as well as this copyright and license information must be included.
![](http://writinghelp.online/777/templates/cheerup/res/banner1.gif)
IMAGES
COMMENTS
The generalized assignment problem (GAP) and its special cases multiple knapsack1 and bin packing2 capture several fundamental optimization problems and have many practical applications in computer science, operations research, and related disciplines. The (offline) GAP is defined as follows: Definition 1 (Generalized Assignment Problem).
Motivated by such needs, we study the online versions of the famous generalized assignment problem (GAP) and the packing problem (also known as d-GAP) in the classic random order model, where the online items arrive over time randomly and uniformly and request specific offline resources.
We present a \ (1-\frac {1} {\sqrt {k}}\) -competitive algorithm for the online stochastic generalized assignment problem under the assumption that no item takes up more than \ (\frac {1} {k}\) fraction of the capacity of any bin. Items arrive online; each item has a value and a size; upon arrival, an item can be placed in a bin or discarded ...
We study an edge-weighted online stochastic \emph {Generalized Assignment Problem} with \emph {unknown} Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline bin is associated with a D -dimensional capacity vector and each online item is with a D -dimensional demand vector.
Highlights โขStudy the online generalized assignment problem in the random order model.โขUse historical information to boost the performance of online algorithms.โขDesign competitive algorithms and co...
Online generalized assignment problem and its various simplified settings such as online bin packing and online knapsack problems have been studied extensively in the literature [Alaei et al ...
Online Generalized Assignment Problem (GAP) is a fundamental research topic in resource allo-cation, which has been widely studied in various areas including operations research and computer science Alaei et al. (2013), Naori and Raz (2019), Albers et al. (2020), Jiang et al. (2021). In this problem, we are given a set of offline bins with general capacities. During the online process, online
The online generalized assignment problem with service consecution constraint studied in this paper is motivated from practical applications. For example, in military one well-known ground weapon is the so-called multiple launch rocket system (MLRS), which consists of a couple of rocket launchers that coordinate with each other during a ...
We study an edge-weighted online stochastic Generalized Assignment Problem with unknown Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline binโฆ
Online Generalized Assignment Problem (GAP) is a fundamental research topic in resource alloca- tion, which has been widely studied in various areas including operations research and computer
This study proposes OCRSs for online stochastic generalized assignment problems, and presents an algorithm with an acceptance probability of $1/2$ and proves that no algorithm can achieve anaccept probability greater than $3/7$. Expand.
Generalized Assignment Problem One of the best known and widely researched problems in combinatorial optimization is Knapsack Problem: given a set of items, each with its weight and value, select a set of items maximizing total value that can fit into a knapsack while respecting its weight limit.
Solve an assignment problem online Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.
Generalized assignment problem In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other.
We also extend the online algorithm to variations of knapsack problems, include the multiple knapsack problem, the multiple-choice knapsack problem, and the generalized assignment problem, and discuss about their applications to sponsored search auctions1.
Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals. We study an edge-weighted online stochastic Generalized Assignment Problem with unknown Poisson arrivals. In this model, we consider a bipartite graph that contains offline bins and online items, where each offline bin is associated with a D-dimensional capacity ...
The generalized assignment problem (GAP) seeks the minimum cost assignment of n tasks to m agents such that each task is assigned to precisely one agent subject to capacity restrictions on the agents. The formulation of the problem is: where \ ( c_ {ij} \) is the cost of assigning task j to agent i , \ ( a_ {ij} \) is the capacity used when ...
Problem Description: Recall the Generalized Assignment Problem (GAP) from last lecture. In this problem we are given a set J of
Motivated by such needs, we study the online versions of the famous generalized assignment problem (GAP) and the packing problem (also known as d-GAP) in the classic random order model, where the ...
Generalized assignment problem is NP-hard, so I'm not trying to find an exact solution. Are there any approximation algorithm or heuristic to solve this problem?
S.P. Wilcox, 'A new multiplier adjustment method for the generalized assignment problem,' Working Paper, General Research Corporation, 7655 Old Springhouse Road, McLean, Virginia 22102, 1989.
21 I can't seem to find any literature on algorithms which can be used to solve a many-to-many generalized assignment problem (GAP), i.e. models where not only can more tasks be assigned to one agent, but multiple agents can also be assigned to one task (one-to-one and one-to-many AP's are discussed in a paper by Pentico). I know next-to-nothing of assignment problems, but I came upon a ...
One such strategy is the use of online discussion forums to provide ICBT clients with opportunities for mutual social support. Self-guided interventions accompanied by online discussion forums have shown excellent treatment outcomes, but there is a need for research experimentally testing the impact of online discussion forums in ICBT.