online generalized assignment problem

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.

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,

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}\} .

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.

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.

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.

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}\} .

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.

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.

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.

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)) .

• 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:

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:

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.

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

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.

Zhenzhen Yan

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.

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

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

• 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:

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).

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 ].

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.

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 .

a SRS: Session Rating Scale.

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 .

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

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.