1

Online Weighted Bipartite Matching with Capacity Constraints

59
60

2

61

3

Hao Wang, Zhenzhen Yan, Xiaohui Bei
62

4

Nanyang Technological University
Singapore

5
6

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

66

ABSTRACT

Once the capacity is used up, it becomes unavailable in demand fulfillment. This new generation of ridesharing significantly increases
vehicle occupancy rates and the efficiency of urban transportation
systems, consequently reducing congestion and pollution.
In the grab hitch platform, drivers are not allowed to pick up
passengers by themselves via self-arrangements, but can only takeride requests assigned by the platform. Therefore, one key problem
faced by the platform is to automatically match ride requests toavailable drivers in real-time so as to maximize the total profit.
A rich literature has been devoted to the study of online matchingalgorithms with different models and under different assumptions.
Karp et al. [19] first studied the online bipartite matching problem
to maximize the number of matches under the assumption that thearrival process is determined by the adversary. In their paper, eachresource has a single unit of capacity and each request is assumed
to consume only one unit of resource. Feldman et al. [14] revisitedthe problem by assuming the arrival process to be stochastic, thatis, the arrival of online vertices follows a known independent andidentical distribution (i.i.d). Brubach et al. [8] extended the earlier
work to the model to maximize the vertex-weighted sum of matches
and the edge-weighted sum of matches. They again assumed unit
demand size for each online request and unit capacity for eachoffline resource. However, in practice, the resources often havegeneral capacities, and each request may consume multiple unitsof capacity in one match. The ride hitch problem described earlier
is an example. Different cars have different number of vacancies toaccommodate passengers. Each ride request could involve multiple
passengers, hence occupy multiple vacancies. The model studied inthis paper considers such a general problem settings. We assume
there are multiple types of resources and each type of resource
has a general capacity. Each online request consumes a single typeof resource but by multiple units. We also assume an i.i.d arrival
process. Our goal is to maximize the edge-weighted sum of matches.
To the best of our knowledge, this is the first paper considering theonline matching problem in such a general setting.

We investigate an online edge-weighted bipartite matching problem
with capacity constraints. In this problem, the supply vertices are
offline with different capacities. Demand vertices arrive online andeach consumes a certain amount of resources. The goal is to maximize the total weight of the matching. This framework can capture
several real-world applications such as the trip-vehicle assignment
problem in ridesharing. We model the offline optimization problem
as a deterministic linear program and provide several randomized
online algorithms based on the solution to the offline linear program. We analyze the performance guarantee of each algorithm
measured by its competitive ratio. Importantly, we introduce a resolving heuristic that periodically re-computes the offline linear
program and uses the updated offline solution to guide the online
algorithm decisions. We find that the algorithm’s competitive ratio
can be improved when re-solving at carefully selected time steps. Finally, we investigate the value of the demand distribution in further
improving the algorithm efficiency.

27
28

KEYWORDS

29
30

online bipartite matching, randomized algorithm, re-solving heuristic, competitive ratio

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

64
65

7
8

63

1

INTRODUCTION

In a typical online bipartite matching problem, requests arrive sequentially following some probability distribution. Upon the arrivalof each request, a decision has to be made to either match the request to an appropriate resource, or reject it. If the request gets
matched, it consumes a certain amount of resources. Resources
can be replenishable or non-replenishable. Each match made between the request and the resource generates a profit. The goal is
to maximize the total profit generated from all matches.
The online bipartite matching has been widely applied to various resource allocation problems. Examples include airline seat
allocation, clinic appointment slot allocation, and car allocation in
the online ride hitch problem. Particularly, ride hitch is a recent
innovation of ride sharing. It refers to a mode of transportation inwhich private car drivers offer to share their journeys to multiple
passengers based on coordination through a centralized dispatch.
For example, drivers may share part of their ride on the way towork with other passengers who have similar itineraries, and thedrivers will receive remuneration to compensate the petrol andlabor costs. An example is the grab hitch service launched by Grab
in 2015, the leading super app in Southeast Asia. A ride request
may involve multiple passengers. In each trip, a driver could takemultiple ride requests as long as the capacity permits. Each ride
trip of a driver can be regarded as a non-replenishable resource.

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

Our Contribution
To solve this general online matching problem, we start by proposing a simple randomized algorithm based on linear program rounding. The algorithm allocates an appropriate resource to each request
with certain probability that is based on the solution of an offline
linear program. We analyze the performance of this simple algorithm. Following the convention in the literature, we measure theefficiency of an online algorithm by the competitive ratio, which isdefined as the total profit generated from the algorithm, divided by
the maximum profit achievable if full information on the arrivalof demand requests is known beforehand. Next, as the main resultof this paper, we introduce a re-solving heuristic to the randomized algorithm. The idea of re-solving is to periodically re-compute
1

103
104
105
106
107
108
109
110
111
112
113
114
115
116

Conference’17, July 2017, Washington, DC, USA

117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

Wang, et al.

the offline linear program and uses the updated offline solution to
guide the online algorithm. We show that re-solving at a right time
could help significantly improve the performance of the algorithm.
We also investigate the value of demand distribution of the online
request to further improve the algorithm’s efficiency.
Finally, we conduct extensive experimental studies to test theefficiency of our proposed algorithms. On average, our online algorithm achieves 70% − 80% of the optimal profit on both synthetic
and real-world datasets. In particular, the proposed randomized
algorithm with the re-solving heuristic significantly outperforms
all the other algorithms. We observe that by re-solving the linear
program at our proposed time, the profit obtained is increased byalmost 20% compared with the standard randomized online algorithm. We also show that the advantage of our proposed algorithms
becomes more salient when the demand in the market increases.
We summarize our main contributions as follows:(1) We solve a general online bipartite matching problem where
the offline resources are equipped with multiple capacities andeach online request consumes multiple units of capacity once
matched. The arrival process is assumed to be i.i.d and the goal
is to maximize the edge-weighted sum of matches.
(2) We propose a randomization algorithm based on the solution to
an offline linear program and establish its competitive ratio asa function of the maximal demand among requests. In a special
case that the maximal demand is 2, the competitive ratio is 14 ,which is comparable to the existing results on similar problem
settings.
(3) We further introduce a re-solving heuristic to the randomization algorithm and show that re-solving at the right time could
significantly improve the performance of the algorithm.
(4) We investigate the value of demand distribution of the online
request to further improve the algorithm’s efficiency.

related work is Xu et al. [27].In their paper, there are multiple typesof resources and each request could consume at most one unit ofeach type. The objective is to maximize the vertex-weighted sum
1 comof matches. They designed an algorithm which achieves 4∆
petitive ratio, where ∆ denotes the maximal number of resources
requested by arrivals. Although their paper shares a similar setting
to ours, our paper distinguishes from theirs in the following aspects:
First, the profit in our paper is defined on edges instead of vertices.
The edge-weighted matching is known to be much more nebulous
than the vertex-weighted case [13]. Second, we assume each arrival
only requests one type of resource but could consume multiple
units of resources.
Another relevant problem to online bipartite matching is theonline generalized assignment problem. In the online generalized
assignment problem, there are m (static) bins each with a capacity
limit. Items arrive online and consume some capacity of the assigned
bins. Alaei et al. [4] provided an algorithm for this problem with
1 − k1 competitive ratio, assuming that no item consumes more than1
k fraction of any bin’s capacity. Kesselheim et al. [20] and Naori etal. [26] considered the online generalized assignment problem in
the random arrival model and provided the best-known competitive
1 .
ratio of 6.99
Other extensions include generalizing the graph to a general
network structure and allowing a matching delay, i.e. the request
is allowed to wait for some time before being matched (c.f. Chenet al. [9], Adamczyk et al. [1], Adamczyk et al. [2], Baveja et al.
[7], Mehta et al. [24], Ashlagi et al. [5], Dickerson et al. [12] andLowalekar et al. [21]).

3

152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

MODEL

177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

204
205

We define our online bipartite matching problem in a ride hitch
context. Consider a bipartite graph G = (U , V , E), where U denotes
the set of drivers’ offers and V denotes the set of possible riders’requests. Each offer u ∈ V is associated with a capacity cu , andeach request v has a demand dv . An edge (u, v) exists for u ∈ U
and v ∈ V if the offer u can can be matched to the request v. Theedge is also associated with a weight (i.e. revenue) wuv .
In our problem definition, we will treat drivers’ offers as offline
resources and riders’ requests as online demands. This is because
generally, the driver has a much longer time tolerance to be matched.
He/She might plan to pick up some friends in the evening but put
up an offer in system in the morning. In contrast, a rider’s request
usually needs to be matched in seconds. If no suitable drivers canbe found within one minute, the request will be rejected.
We assume an i.i.d. distribution model of request arrival overan online time horizon of T rounds. That is, the set U is madeavailable offline beforehand. In each round, a rider request v is
sampled with replacement from a known distribution {pv } over V .
The distribution is independent and identical in every round. Upon
the arrival of request v, a decision has to be made to either reject v,
or to match it to some neighbor offer u ∈ U that still has enoughremaining capacity. If a pair (u, v) is matched, a revenue of wuv isgenerated and the capacity of u is decreased by dv .
Below is the list that summarizes the notations.

150

2

176

203

149

151

175

RELATED WORK

The problem of online bipartite matching has been intensively studied, and the literature is too vast to survey here. We provide an
overview of the work most directly relevant to ours. The first algorithm for the single-capacity unweighted online bipartite matching problem was given by Karp et al. [19]. They introduced the
RANKING algorithm and proved a tight 1 − e1 competitive ratiowith adversary online vertex arrival order. The analysis was later
simplified by Devanur et al. [11]. Aggarwal et al. [3] generalized
the problem by considering weigthed offline vertices. Mehta et al.
[25] investigated the multi-demand case known as the AdWords
problem and presented a 1 − e1 competitive algorithm.
Another line of works considers the random arriving model,
in which the online vertices arrives in a uniformly random order.
Karande et al. [18] and Mahdian et al. [22] independently showedthat the RANKING algorithm can achieve a competitive ratio better
than 1 − e1 in the random arrival model. Huang et al. [16] further
generalized the analysis to the vertex-weighted setting. Devanurand Hayes [10] presented a 1 − ϵ competitive algorithm for the
AdWord problem in the random arrival model.
Finally, a third line of works, which also includes this work, assumes the arrival of online vertices follows a known independentand identical distribution [6, 14, 15, 17, 23]. In this model, a closely

206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229

• T : total numbers of online requests.
• pv : the probability of type v vertex in each arrival.
2

230
231
232

Online Weighted Bipartite Matching with Capacity Constraints

233
234
235
236
237

Conference’17, July 2017, Washington, DC, USA• dv : the demand of online request v.
• D: the maximal demand of all online requests.
• cu : the capacity of offer u.
• C: the maximal capacity of all offers.
• wuv : the weight (i.e., revenue) associated with edge (u, v)

Algorithm 1: Samp(α) Algorithm
Result: Online matchings M
Solve the LP (3) and get the optimal solution y ∗ ;Time t = 1;
Matchings M = ϕ;while t ≤ T do
Online vertex v arrives;∗ ;Randomly choose u with probability αyuv
if cu ≥ dv thenMatch u and v: cu = cu − dv , M = M + (u, v);
else
Reject v;
end
t = t + 1;
end

238
239
240
241
242

MILP formulation. Given a realized arrival sequence s of requests,
we can solve a mixed integer linear program (MILP) to optimally
match them to the offers.
Õmax
wuv Xuv (s)243(u,v)∈E

244

Õ

245

s.t.

dv Xuv (s) ≤ cu , ∀u ∈ Uv:(u,v)∈E

246

Õ
247

(1)
Xuv (s) ≤ Nv (s), ∀v ∈ V

248

u:(u,v)∈E

249

Xuv (s) ∈ {0, 1}, ∀(u, v) ∈ E

252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

280

v:(u,v)∈E

282

Õ

283

pv dv yuv ≤cu, ∀u ∈ UT

u:(u,v)∈E

285

yuv ≥ 0, ∀(u, v) ∈ E

289
290

297
298
299
300
301
302
303
304
305
306

308
309
310
311

313
314
315
316
317
318
319
320
321

E[Cut ] =≤t −1 Õ
Õt ′ =1 v ′ ∈V
t −1
Õ
αcu
t ′ =1T∗
pv ′ αyuv′ dv ′ ==t −1 Õ
Õt ′ =1 v ′ ∈V

322

∗
αyuv
′ dv ′ pv ′

323

(4)

αcu (t − 1)
T

324
325
326
327

where the last inequality is from offline vertex’s capacity constraint.
By Markov’s inequality, we can write the probability that v ismatched to u at time step t as


αcu
∗
Pr α (u, v, t) ≥ αpv yuv
1 − (t − 1)
T (cu − dv + 1)

328

This allows us to bound the expected number of times that edge(u, v) is matched by the algorithm during the first t ′ steps.

334

329
330
331
332
333

335
336

N α (u, v, t ′ ) ≥
(3)

t′
Õ
t =1
t′
Õ

337

Pr α (u, v, t)

338
339





αcu
T
(c
−
dv + 1)
u
t =1
"  
#
2
t′
α 2c ut′∗≥ −+ α Tpv yuv
T2(cu − dv + 1) T"  #t ′ 2 α 2D t ′∗≥ −+ α Tpv yuv
T
2
T

=

We use OPT to denote the optimal value of (3).

287
288

296

Our first online algorithm takes a common linear-program-rounding∗ from (3). Then for
approach. First solve the optimal solution yuv
each arrival request v, an offer u is randomly chosen to match v∗ . Here α is a parameter that controls how
with probability αyuv
aggressively the online algorithm makes the matches.
Let Cut denote the amount of capacity of offer u consumed by
the requests before time t. We haveyuv ≤ 1, ∀v ∈ V

284

295

A RANDOMIZED ALGORITHM — SAMP (α)(u,v)∈E

281

286

4

Noticed that OF F (s) of (1) is a concave function in Nv (s) for eachsequence s. By taking the expectation over all possible arriving
sequences, replacing E[Nv (s)] by pv T , and defining yuv = pxvuvT ,we get upper bound E[OF F ] by the following linear program.
Õmax
Tpv wuv yuv
Õ

294

312

Competitive Ratio Analysis. Note that one usually cannot achieve
E[OF F ] via an online algorithm due to an unforeseen circumstance in the future. In this paper, we aim to design online algorithms to achieve as a larger expected revenue as possible. To
evaluate the performance of an online algorithm L, we adopt acommonly used performance criterion— competitive ratio (CR). For
a given sequence s, we denote the outcome achieved by an algorithm L as ALG L (s). Then the expected outcome by the algorithm isÍ
E[ALG L ] = s P(s)ALG L (s). The competitive ratio of an algorithm
L is defined as
E[ALG L ]CR L =(2)
E[OF F ]

s.t.

293

307

Here Nv (s) denotes the number of type v vertex appeared insequence s. The first set of constraint restricts the total consumptionof each resource u below its capacity and the second set of constraint
specifies the matched request cannot exceed the total arrivals.
We denote the optimal solution to (1) as H (s) and the optimal
objective value as OF F (s). Then the expected revenue generated by
optimally solving each possible arrival realization can be formulatedÍ
as E[OF F ] = s P(s)OF F (s), where P(s) denotes the probability ofsequence s among all possible sequences.

279

292

We omit the proof due to space constraints.
In the subsequent sections, we will use linear program (3) to aid
our design of the randomized online algorithms and analyze theircompetitive ratios.

250
251

291

Proposition 3.1. OPT ≥ E[OF F ], i.e., E[OF F ] is upper boundedby the optimal value of (3).
3∗
αpv yuv
1 − (t − 1)

340
341

(5)

342
343
344
345
346
347
348

Conference’17, July 2017, Washington, DC, USA

349
350
351
352
353
354
355
356

The last inequality holds as 1 ≤ cu ≤ C and 1 ≤ dv ≤ D andcu ≥ dv , which implies that for every u and v,(u,v)∈E
 2
α D

358

≥ −

359

2
360

+α



Õ
(u,v)∈E

366

3
8

408

410
411

Next we study the effect of re-solving heuristic. Suppose we re-solve
the linear program after the first arrival. Consider such a realized
sequence s 0 = (v 1 , v 1 , v 0 , v 0 ). The re-solved LP will suggest to
accept v 0 with probability 1 and accept v 1 with probability 13 fromthe second arrival on. Hence the expected profit generated under
this sequence is 23 ×2w + 13 (1+w) by the re-solving method, which isequivalent to say the expected loss compared to the offline optimal
solution is w3−1 . Noticed that the probability of having a sequence
1 . Then we can upper bound the expected outcome ofs = s 0 is 16
this re-solving method as follows

 Õ
w −1
E[ALG ′ ] ≤ P(s 0 ) OF F (s 0 ) −+P(s)OF F (s)
3
s,s



(6)
Proposition 4.1. The Samp(α) algorithm has competitive ratio
1 .
CR ≥ 2D

364
365

407

409

E[OF F ] = E[ALG] + 2q 0 + q 1 = E[ALG] +


α 2D
∗
+ α OPT
Tpv wuv yuv
≥ −
2

361

363

sequence has less than two v 0 . According to the i.i.d assumption,
1 and q = 1 . Therefore we have:
we have q 0 = 16
14

dv − 1
D−1
cu
=1+
≤ 1+
= D.
c u − dv + 1
c u − dv + 1
1
Therefore, we can further bound the expected performance of theSamp(α) algorithm as follows.
Õ
ALG α =
[wuv N α (u, v,T )]

357

362

Wang, et al.

The proof of the proposition is a straightforward result from theanalysis above and is omitted here.

412
413
414
415
416
417
418
419
420
421
422
423
424

0

367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382

4.1

Re-solving Heuristic≤ E[OF F ] −Note that in algorithm Samp(α), the linear program (3) is solved
once at the beginning of the algorithm. Then the solution will be
used to guide the online algorithm matching probability throughout
the whole time span. However, in the middle of the process, due
to the randomness of the request arriving sequence, it is probablythat the capacities of the orders are consumed disproportionately.
In such cases, the original LP can no longer capture the correct
resource configuration. As such, we need to re-solve the linear
program with the updated capacity information, and update the LP
solution to guide the subsequent allocation. We call this refinement
step the re-solving heuristic.
In this section, we will analyze the re-solving heuristic. Our goal
is to decide whether and when this heuristic will improvement thealgorithm performance.

385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406

425
426

By setting w > 19, we have E[ALG ′ ] < E[ALG]. In other words,

427
428

to re-solve LP could generate a worse performance.
429

4.1.2 Re-solving at the right time helps. In this section we focus on
the problem of when to re-solve. Consider the following question: if
we are only allowed to re-solve the LP once during the whole timespan, when should we re-solve the LP to maximize the expected
performance of the algorithm? Suppose we re-solve at time t ′ =(1 − β)T = γT . Let T ′ denote the remaining time period. Then
T ′ = βT . Let Xu denote the remaining capacity of u at time t ′ . Thenthe new LP becomesÕmax
T ′pv wuv yuv ,(u,v)∈E

383
384

w −1
48

s.t.

4.1.1 Re-solving does not always help. First we try to answer thequestion of whether the re-solving heuristic, regardless of when it
is applied, always helps the algorithm to generate a better solution.
Intuitively this may seem true. However, in the following we show
via a counterexample that the re-solving heuristic may make things
worse sometimes.
• 1 offline vertex: c = 2• 2 online vertices: v 0 and v 1• v 0 : p0 = 12 , d 0 = 1, w 0 = w > 1• v 1 : p1 = 21 , d 1 = 1, w 1 = 1• T =4In this case, D = 1 hence α = D1 = 1. By solving the offline
LP (3), we know that algorithm Samp will always accept v 0 as longas the capacity permits and reject v 1 . To understand the performance of algorithm Samp, let s denote the realized sequence. If
s = (v 1 , v 1 , v 1 , v 1 ), then the offline optimal profit is 2 while Samp
gives 0. If there is exactly one v 0 in s, the offline optimal profit is
1 + w while Samp gives w. If there are more than one v 0 in s, bothoffline optimal profit and the expected profit by Samp are 2w. Let q 0
denote the probability that s has no v 0 and q 1 denote the probability
that s has one v 0 . In summary, the expected profits generated by
the offline linear program and Samp are different only if the realizedÕ
v:(u,v)∈E

Õ

430
431
432
433
434
435
436
437
438
439
440

Xu
pv dv yuv ≤ ′ , ∀u ∈ U ,
T

441
442

(7)
yuv ≤ 1, ∀v ∈ V ,

443
444

u:(u,v)∈E

445

yuv ≥ 0, ∀(u, v) ∈ E

446

yuv = 0, ∀(u, v) ∈ E, Xu < dv .

447
448

We add the last constraint because when running the algorithm
for several rounds, some offline vertex might have less remaining
capacity than the demand. In this case, the edge between them still
exists but the matching is not possible. Denote the optimal solutionof the re-solved linear program as y ′∗ and the optimal value as
OPT ′ . The optimal solution and optimal value of the new linear
program depend on the remaining capacity, which is a random′variable. Hence the optimal solution y ∗ and optimal value OPT ′are also random variables. To simplify the analysis, we condition ona particular realization of the remaining capacity in the subsequent′
presentation, i.e. Xu = cu′ , in which case, y ∗ and optimal value′
OPT are deterministic.
Let N α′ (u, v,T ) be the expected number of (u, v) that is matched by
re-solved algorithm, which is to match the resource based on αy ∗′before t ′ and on α 1y ∗ after t ′ . Following a similar analysis above,
4

449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464

Online Weighted Bipartite Matching with Capacity Constraints

465
466
467
468
469
470
471

Conference’17, July 2017, Washington, DC, USA

we have from the re-solve point t ′ , the expected match between aresource-request pair (u, v) can be analyzed as follows:"#
α 12cu′
′∗
T′
T′ 2
′
′
N α (u, v,T ) ≥ −( ′ )+ α 1 Tpv yuv
T2(cu′ − dv + 1) T ′
(8)
"
#
α 2D
′∗
≥ − 1 + α 1 Tpv yuv
2

4.1.3 Re-solving Many Times At the Right Time Further Helps to
Improve the Bound. Consider such a randomization algorithm. Randomly allocate the resource based on Samp(α) until γT . After ith
re-solve, the allocation is based on Samp(α i ) and the new re-solve
time point is at γ proportion of the remaining time period. We callsuch an algorithm as a log-resolving algorithm with parameter γ
to specify the re-solving time point. Denote the remaining time(i)period at ith re-solve as T (i) . T (0) = T . Let Xu denote the remain(i)ing capacity right before ith re-solve. Notice that Xu is a randomvariable, we first study the bound of the expected ratio between
the optimal values of two consecutive linear programs conditioned(i)on a realization of Xu .

472
473
474
475
476
477
478
479

1 Tp y ′ ∗ . The
By choosing α 1 = D1 , we have N α′ (u, v,T ′ ) ≥ 2Dv uv′∗
second inequality holds as yuv = 0 if cu′ < dv , which implies
′∗
c′
v −1
≤ dv .
for any yuv> 0, cu′ ≥ dv , hence c ′ −du +1 ≤ 1 + c ′ d−d
v
v +1
u

u

Therefore,

(i)


′∗
α 2D 2
1∗
N α′ (u, v,T ) ≥ −γ + αγ Tpv yuv+
Tpv yuv
2
2D

(9)

480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507

(i)

Proposition 4.4. Conditioned on Xu = cu , ∀u, under the condition that TR(i ) << 1, we have
OPTi+1 (i)Ec≥ (1 − γ )e −αγ R
(13)
OPTi



The expected outcome of re-solve algorithm is

 2
Õ
1
α D 2
γ + αγ OPT +OPT ′wuv N α′ (u, v,T ) ≥ −
2
2D
uv

510
511
512

Then we can bound the competitive ratio from below, i.e.,
h 2
i
2 2
1 O PT ′ = − γ α D + γ α + 1 O PT ′ .
CR ′ ≥ − α 2D γ 2 + αγ + 2D2O PT
2D O PT(10)′
Now we want to show the lower bound (LB) of OOPT
and
check
if
PT
we need to re-solve according to this LB. We construct a solution
y ′ for LP’ based on the optimal solution of LP. We denote U+ as theset of offline vertices whose capacity without change, i.e., cu′ = cu
and U− as the rest of the offline vertices. Consider such a solution(y∗u ∈ U+′
yuv = uv
(11)0
u ∈ U−

515
516
517
518
519
520
521
522

525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540

542
543
544

Theorem 4.5. The log-resolving algorithm with γ = D1 gives a R
1 1−C K +1 , where C = 1 − 1 e − Dcompetitive ratio at least 2D. This1−CDvalue increases with the number of re-solving time K and converges
1
to 2D(1−C)
when K approaches infinity.

545
546
547
548
549
550

Proof: To start the proof, we first define some notations: denote thetime for ith re-solve as ti , the ratio between the maximal remaining
capacity and the minimum demand as Ri and the optimal value ofthe ith re-solved LP as OPTi . Samp(α) is applied at the beginningand after ith re-solve, Samp(α i ) is applied. ALG(s,T ) denotes the expected outcome from time s to T using the designed randomization
algorithm, which is to match the resource according to the solution
from the corresponding re-solved deterministic linear program ineach time interval. We can derive a lower bound if the expected
performance of our re-solving heuristic in the following way: fromthe beginning of the time period to the first re-solve point t 1 , thelower bound is derived from (5); from t 1 onward the algorithm isbased on the designed randomization algorithm. Therefore,
 2 2

γ α D
E[ALG(0,T )] ≥ −+ γ α OPT + E[ALG(t 1 ,T )]2

It is easy to check that y ′ is feasible for the re-solved linear program(7). Therefore,
OPT ′ T ′ (w ′ (U+ ) + w ′ (U− ))w ′ (U+ )
(12)
≥
=β
OPT
T (w(U+ ) + w(U− ))w(U+ ) + w(U− )Í∗ , w(S) = Í′
where wu = v ∈Ad j(u) pv wuv yuv
u ∈S wu and w (S) =ÍÍ′u ∈S v ∈Ad j(u) pv wuv yuv . Bearing in mind that the remaining
capacity Xu is a random variable, OPT ′ is also random. From theanalysis above, we havehi
O PT ′−αγ R
u cu
Proposition 4.2. Define R = max
min d , E O PT ≥ (1−γ )e
v v

551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566

We omit the proof of the proposition due to space constraints.
Based on the result in Proposition 4.2. Let α = 1 and γ = D1 .
We can further establish the following proposition to demonstratethat re-solving at γT helps to achieve a better lower bound for thecompetitive ratio.

Hence we have
567

E[ALG(0,T )]
O PT

513
514

524

541

We omit the proof here as it is similar to Proposition 4.2. With
this proposition, we are now ready to establish our first main resultin the paper.

508
509

523

γ 2α 2D
E[ALG(t ,T )]≥ − 2 + γ α + h O PT1iγ 2α 2D
ALG(t 1,T ) O PT1= − 2 + γα + E
O PT1
O PT

Notice that the remaining capacity at time t 1 is a random variable,
hence the re-solved LP is also a random variable determined bytheh remaining capacity.
Hence
we can reformulate
the
i
h
i
h
i last term as

Proposition 4.3. Re-solving at TD helps to generate a better comR
1 + 1 (1 − 1 )e − Dpetitive ratio which is CR ′ ≥ 2D
2D
D

ALG(t 1,T ) O PT1
O PT1
O PT

ALG(t 1,T ) (1)1E=Ec· E OOPT
PT . From propoh
iO PT1−αγ R . Hence we have1
sition 4.4, we have E OOPTPT ≥ (1 − γ )e

The first term in the established competitive ratio is exactly theone we have built for algorithm Samp. The second term is nonnegative as long as D ≥ 1, which indicates that to re-solve at our
proposed time will generate at least the same competitive ratio as
Samp(α).

568
569
570
571
572
573
574
575
576
577



γ 2α 2 D
E[ALG(0,T )]ALG(t 1 ,T ) (1)≥−+γα + Ec(1 − γ )e −αγ R
OPT
2
OPT1
5

578
579
580

Conference’17, July 2017, Washington, DC, USA

581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603

608
609

group q, we define the demand distribution as pl |q = pqlq , where
Í
Í
pql =
pv and pq =
pql .

l0

612
613
614

1− (1−γ )e


K
R i
Í
1
1
−D
= 2D
≥
2D (1 − γ )e

i=0
1
→ 2D

1−(1−γ )e

R
−D

1
= 2D

(

)e

617
618
619
620
621

 K +1
R

R
−D

626
627
628
629
630
631
632
633
634
635
636
637
638

652

−1 ≤ l since l ≤ c .
as c c−lu +1 ≤ 1 + c l−l
u
+1
u
u
2l
′
′
α
t
t
2
′
Let Al (t ) = −( T ) 2 + T α and Al (t ′ ) is decreasing in l for
any 0 < t ′ ≤ T .

Then write down the expected outcome of this algorithm:Õ
ALG α =
[wuq N α (u, q, l,T )]With Information of Demand Distribution

654

656
657
658
659

Previous section has established the competitive ratio as a function of the maximal demand. But we have not made use of thedemand distribution. To see the value of the information, we first
aggregate the type of each online arrival as follows: For online vertices with the same adjacent offline vertices and the same weight
for each corresponding incident edges, we aggregate them into agroup. In other words, the set defined by Q(v) = {v ′ | Adj(v ′ ) =Adj(v), wuv ′ = wuv , ∀u ∈ Adj(v)} contains all the online vertices
in the same group as v. Then we can distinguish online arrival
vertices by its affiliated group and demand size. We denote thewhole set of groups as Q and the demand set in group q as Lq . For
any vertex v ∈ V, its group is defined by q(v) ∈ Q. The probabilityÍof getting a vertex in group q ∈ Q is
pv . For vertex in

≥

Õ
u,q,l

≥
=

663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679

682
683

∗
Tpql wuq Al (T )yuql

Õ ÕTpql Al (T )Õq ∈Q l ∈LquÕ ÕTpql Al (T )Wql

684∗
wuq yuql(17)

For notation simplicity, we omit T and use Al to denote Al (T ). To
further analyze the lower bound, we first establish some propertiesÍ∗of vertices in the same group. We define Wql = u wuq yuql
fora fixed group q to represent the expected profit generated by thevertices in the group.
6

662

681

q ∈Q l ∈Lqv ∈V:q(v)=q

661

680

u,q,l

624
625

650

660

4.1.4 Time Complexity. For each arrival, the matching decision isdone by flipping a coin based on the optimal solution to a linear program and checking the capacity availability. Hence the computation
efficiency is mainly determined by the computation time of a linear
program. For Samp(1), we need to solve O(1) linear programs, andit requires O(log |V |) linear programs for the re-solving heuristic.

4.2

649

651

In other words, we can regard the vertices in the same group andcapacity as a super vertex with arrival probability pql and solve
the revised linear program. For each arrival, a resource is matchedaccording to the revised linear program. The randomization algorithm based on the revised linear program will generate the same
results as the original linear program. In the following analysis,
we will focus on the revised linear program. Denote the optimal∗ for each u, q, l.
solution to (15) as yuql′
Let N α (u, q, l, t ) be the expected number of matched edge (u, q, l)from t = 1 to t = t ′ . Following a similar analysis to (5), we havet′
α 2c ut′∗
N α (u, q, l, t ′ ) ≥ −( )2+ α Tpql yuql
T 2(cu − l + 1) T(16)t ′ α 2l t ′∗≥ −( )2+ α Tpql yuql
T
2
T

622
623

648

655

615
616

647

u ∈Ad j(q,l )Lemma 4.7. (15) is equivalent to (3). Specifically, For all v thatq(v) = q, dv = l, we have an optimal solution y ∗ to (15) such that∗∗ for every adjacent vertex u, where y ∗ is an optimal
yuql
= yuv
uv
solution to (3).

1
1− 1− D1646

653

1−(1−γ )e − D1644

yuql ≥ 0, ∀(u, (q, l)) ∈ E
We prove in the following lemma that the revised LP is equivalentto (3).

0, . . . , K − 1. Aggregate all the inequalities, we have

611

643

645

Then we can revise the linear program (3) accordingly as belowÍÍ
max
Twuq pql yuqll(u,(q,l ))∈E
Í Í
s.t .
pql lyuql ≤ cTu , ∀u ∈ U
q ∈Q l ∈Lq(15)
Íyuql ≤ 1, ∀(q, l) ∈ V

α2 D
and l K ≥ − K2 + α K . Set α K = D1 , α i = 1, ∀i = 0, ..., K − 1 and
1 and l ≥ 1 + l−R
γ = D1 . We have l K ≥ 2Di
i+1 (1 − γ )e D , ∀i =
2D
R
−D

640

642

Lemma 4.6. There exists an optimal solution to (3), such that yuv =yuv ′ is q(v) = q(v ′ ) and dv = dv ′ .

γ 2α 2Dli ≥ − 2i + γ α i + li+1 (1 − γ )e −α i γ R , ∀l = 0, ..., K − 1



639

641

From the definition of groups, it is easy to get

ALG(t ,T )Denote E[ O PTii | c (1) , . . . , c (i) ] as li . Hence we have

610

l ∈Lq

v ∈V:q(v)=q,dv =l

In the last period, we have
α2 D
ALG(t K ,T ) (1)c , . . . , c (K ) ≥ − K + α K
E
OPTK
2

605

607

p

h
i
ALG(t 1,T ) (1)
Conditioning on c (1) , OPT1 is deterministic, hence Ec
O PT1
represents the expected performance of the randomization algorithm. Starting from t 1 , we can follow a similar analysis to get thefollowing inequalityhi
ALG(t 1,T ) (1)
E
c
O
PT
1


h
i
γ 2α 2D
ALG(t 2,T ) O PT2 (1)≥ E − 21 + γ α 1 c (1) + E
c
O PT2 O PT1hiγ 2 α 12 D
ALG(t2,T ) (1)≥ E − 2 + γ α 1 c (1) + E
c , c (2) (1 − γ )e −α 1γ R
O PT2
h
i
γ 2α 2D
ALG(t 2,T ) (1) (2)≥ − 21 + γ α 1 + E
c ,c(1 − γ )e −α 1γ R
O PT2
(14)
With the same analysis we have for each i,hi
γ 2α 2D
ALG(t i ,T ) (1)E
c , . . . , c (i) ≥ − 2i + γ α i +
O
PT
i
h
i
ALG(t i +1,T ) (1)E
c , . . . , c (i+1) (1 − γ )e −α i γ R
O PTi +1

604

606

Wang, et al.

685
686
687
688
689
690
691
692
693
694
695
696

Online Weighted Bipartite Matching with Capacity Constraints

697
698

Conference’17, July 2017, Washington, DC, USA

Lemma 4.8. If q(v) = q(v ′ ) = q and dv = l < m = d v ′ , thenWql ≥ Wqm .

If the number of re-solving time K increases the ratio can be better.
When K is large, this ratio converges toLemma 4.8 indicates that within the same group, the vertices
with a smaller demand generates a higher expected profit. Basedon such an observation, we can build the following lemma.
ÍLemma 4.9. For each type q ∈ Q, given a fixed
Tpql Wql , we

1
1
2Me 1 − (1 − 1 )e − MRe

701
702
703

706

709
710

713

5

716
717

Denote Me = maxq ∈Q E[Dq ]. Then we are ready to present
a new lower bound of the Samp(α) when demand distribution isavailable.
Theorem 4.10. With the distribution of demand, Samp(α) generates a competitive ratio 2M1 e , where Me = maxq ∈Q E[Dq ].
Proof: From Lemma 4.9, we have for all possible type q,Õ11
Tpql Al Wql ≥ (−E[Dq ] α 2 + α)Wq ≥ (−Me α 2 + α)Wq
2
2
l ∈Lq

718
719

Therefore, q ∈Q l ∈Lq Tpql Al (T )Wql ≥ (−Me 12 α 2 +α) q ∈Q Wq =(−Me 21 α 2 + α)W . In other words, the competitive ratio is lower
bounded by −Me 12 α 2 +α. By setting α = M1e , we can get a constanta competitive ratio 2M1 e .

720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741

Í

Í

4.2.1 Re-solve with Demand Distribution. With information of demand distribution, we can again apply the re-solving heuristic to see
whether we can further improve the competitive ratio. According
to Lemma 4.7, the deterministic linear program (3) can be reformulated as (15). When revolving the problem, the deterministic linear
program can be revised accordingly as follows:ÍÍ
max
Twuq pql yuqll(u,(q,l ))∈EÍ Ís.t.
pql lyuql ≤ cTu , ∀u ∈ U
q ∈Q l ∈LqÍ
(18)
yuql ≤ 1, ∀(q, l) ∈ V

where S denotes the set of sampled request sequences and P L (s)denotes the profit by algorithm L for the sequence s. Noticed thatdifferent algorithms share the same offline optimal profit, the comparison of empirical competitive ratio is equivalent to a comparisonof profit. For a given bipartite graph G and a planing horizon T ,we generate M request sequences by uniformly sampling each request from the demand pool. We run tests for T = k |V | wherek = 1, 2, 3, 4, 5.
The test is organized in the following manner: We first test
different algorithms in New-York city taxi data, with the request
weights ranging from 1 to 5. We examine the performance of eachalgorithm in different markets and investigate the effect of different
re-solving time points. Lastly, we extend the test to some synthetic
data generated and test different request weight ranges.
The first column of Figure 1 presents the performance of different algorithms in different markets. The parameter k and r indicate
the unbalance between the supply and demand in the market. The
larger they are, the more overwhelming the demand is. From thefigure we can see that in general, the re-solving method outperforms both greedy method and Samp(1) algorithm. On average,
incorporating re-solving heuristic in the randomization algorithm
improves the profit by 20%. Greedy method performs well when
demand is not high. But its performance drops significantly whenu ∈Ad j(q,l )yuql ≥ 0, ∀(u, (q, l)) ∈ Eyuql = 0, ∀(u, (q, l)) ∈ E, cu < lFollow a similar analysis in the previous section, we have#"  t ′ 2 α 2 Me t ′1
E[ALG(0,T )] ≥ −+ α OPT +E[OPT ′ ]
T
2
T
2Me
(19)

742
743

Following a similar analysis to Proposition 4.3, we can easily derive744

the new competitive ratio 2M1 e + 2M1 e (1 − M1e )e − Me if re-solving

R

745
746

once at MTe . The same analysis applies to the case with multiple
times of re-solve.

747
748
749
750

Theorem 4.11. When demand distribution is available, the logresolving algorithm with γ gives a competitive ratio after Kth re-solve
is:


R

751
752
753
754

762
763

l ∈Lq

Í

EXPERIMENT

We test the online algorithms proposed in Section 4 over several
synthetic data sets and a New York city taxi data set. Each data
set specifies a bipartite graph, which is represented by G(U , V , E),
where U , V represents the offline and online request set respectively|V |and E denotes the arc set. Let r = |U | denote the ratio between thenumber of online and offline vertices. We compare our algorithms
to the greedy algorithm, which is a widely used benchmark in theliterature (c.f. Xu et al. [27], Dickerson et al. [12] and Lowalekar etal.[21]). Specifically, we analyze the following algorithms in thissection.
• Greedy: Assign an arriving request v to the resource u withthe largest weight on the edge (u, v) among all the available
resources; if no available resource found, reject v.
• Samp(1): Refer to the Samp(α) algorithm and choose α = 1.
• RES-γ : Under the Samp(1) framework, update the offline linear
program at t = T (1 − (1 − γ )i ) for 1 ≤ i ≤ K, where K is the
maximal re-solve times. Set K = 10. We test over different γ
including γ = D1 = 13 as D = 3 in the data.
The comparison is based on the empirical competitive ratio (ECR).
The empirical competitive ratio (ECR) is defined as the ratio between
the total profit generated from an algorithm and the total offline
optimal profit for a sample of request sequences.
Í
P L (s)ECR L = Í s ∈S,
s ∈S OF F (s)

714
715

759

761

711
712

758

760

Í
have l ∈Lq Tpql Al Wql ≥ (− 12 E[Dq ]α 2 + α)Wq , where E[Dq ] is theÍ
Tpql Wql .
expected demand of type q arrivals and Wq represents

707
708

Me

l ∈Lq

704
705

756
757

699
700

755

K +1

− Me
1
1 1 − (1 − Me )eR
2Me
1 − (1 − 1 )e − Me
Me

7

764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812

Conference’17, July 2017, Washington, DC, USA

Wang, et al.

813

871

814

872

815

873

816

874

817

875

818

876

819

877

820

878

821

879

822

880
881

823
824

(a) r = 1(b) r = 1(c) Synthetic data: 1 ≤ wuv ≤ 5

882

825

883

826

884

827

885

828

886

829

887

830

888

831

889

832

890

833

891

834

892

835

893

836

(d) r = 2(e) r = 2(f) NYC data, 1 ≤ wuv ≤ 2

894

837

895

838

896

839

897

840

898

841

899

842

900

843

901

844

902

845

903

846

904

847

905
906

848
849
850

(g) r = 3(h) r = 3(i) Synthetic data: 1 ≤ wuv ≤ 2

Figure 1: Result Summary

853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868

demand increases. In contrast, the performance of the proposed randomization algorithms is more robust across different markets. One
possible reason is that when demand is high, strategically skippingsome inferior demand can better utilize the resource capacity.
To further understand how important it is to re-solve at a righttime. We compare algorithms with different re-solving time points.
The second column in Figure 1 compares the performance of algorithms with different γ when applying RES-γ algorithm. From
the figure we can see that resolving at our proposed time whichis to set γ = D1 = 31 outperforms the other time points. It could
achieve up to 12% improvement compared to some other resolving
time. Consistent with the observation in the column in Figure 1, therandomization algorithms gets better performance when γ becomeslarger, for all the tested γ s.
We extend the test to the synthetic data generated and plot theresults in Figure (a) in the last column of Figure 1. The observations
are consistent with those in the first column . We further test thedata with edge weights in a smaller range. It is observed that when
the weight range becomes smaller, online algorithms’ performanceincreases. This observation is more significant when it applies to
the greedy method. It implies that the randomization algorithm ismore robust across different data sets.

910
911
912
913
914
915

6

CONCLUSIONS

916
917

We study the online weighted bipartite matching problem withcapacity constraints in this paper. We propose a randomized algorithm based on the solution to an offline linear program and analyze
its competitive ratio. We further introduce a re-solving heuristic
to the randomized algorithm and demonstrate that re-solving at
the right times could significantly improve the performance of thealgorithm. Finally, we investigate the value of demand distributionof the online request to further improve the algorithm’s efficiency.
Several experiments are conducted to test the performance of the
proposed algorithms based on an application in ride hitch.

918
919
920
921
922
923
924
925
926
927

869
870

908
909

851
852

907

8

928

Online Weighted Bipartite Matching with Capacity Constraints

929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984

Conference’17, July 2017, Washington, DC, USA

REFERENCES[26] David Naori and Danny Raz. 2019. Online multidimensional packing problems
in the random-order model. arXiv preprint arXiv:1907.00605 (2019).
[27] Pan Xu, Yexuan Shi, Hao Cheng, John Dickerson, Karthik Abinav Sankararaman,
Aravind Srinivasan, Yongxin Tong, and Leonidas Tsepenekas. 2019. A Unified
Approach to Online Matching with Conflict-Aware Constraints. (2019).

[1] Marek Adamczyk. 2011. Improved analysis of the greedy algorithm for stochastic
matching. Inform. Process. Lett. 111, 15 (2011), 731–737.
[2] Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. 2015. Improved
approximation algorithms for stochastic matching. In Algorithms-ESA 2015.
Springer, 1–12.
[3] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. 2011.
Online vertex-weighted bipartite matching and single-bid budgeted allocations.
In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete
Algorithms. SIAM, 1253–1264.
[4] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2013. The online
stochastic generalized assignment problem. In Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques. Springer, 11–25.
[5] Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim
Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. 2017. Min-costbipartite perfect matching with delays. Approximation, Randomization, andCombinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
81 (2017), 1–1.
[6] Bahman Bahmani and Michael Kapralov. 2010. Improved bounds for online
stochastic matching. In European Symposium on Algorithms. Springer, 170–181.
[7] Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu.
2018. Improved bounds in stochastic matching and optimization. Algorithmica
80, 11 (2018), 3225–3252.
[8] Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu.
2016. Online Stochastic Matching: New Algorithms and Bounds. arXiv preprint
arXiv:1606.06395 (2016).
[9] Ning Chen, Nicole Immorlica, Anna R Karlin, Mohammad Mahdian, and Atri
Rudra. 2009. Approximating matches made in heaven. In International Colloquium
on Automata, Languages, and Programming. Springer, 266–278.
[10] Nikhil R Devanur and Thomas P Hayes. 2009. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedingsof the 10th ACM conference on Electronic commerce. ACM, 71–78.
[11] Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. 2013. Randomized primaldual analysis of ranking for online bipartite matching. In Proceedings of thetwenty-fourth annual ACM-SIAM symposium on Discrete algorithms. Society for
Industrial and Applied Mathematics, 101–107.
[12] John P Dickerson, Karthik A Sankararaman, Aravind Srinivasan, and Pan Xu.
2018. Allocation problems in ride-sharing platforms: Online matching with offline
reusable resources. In Thirty-Second AAAI Conference on Artificial Intelligence.
[13] Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam.
2020. Edge-Weighted Online Bipartite Matching. arXiv preprint arXiv:2005.01929(2020).
[14] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. 2009.
Online stochastic matching: Beating 1-1/e. In 2009 50th Annual IEEE Symposium
on Foundations of Computer Science. IEEE, 117–126.
[15] Bernhard Haeupler, Vahab S Mirrokni, and Morteza Zadimoghaddam. 2011. Online stochastic weighted matching: Improved approximation algorithms. In International workshop on internet and network economics. Springer, 170–181.
[16] Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. 2018. Online
Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals. arXiv
preprint arXiv:1804.07458 (2018).
[17] Patrick Jaillet and Xin Lu. 2014. Online stochastic matching: New algorithms
with better bounds. Mathematics of Operations Research 39, 3 (2014), 624–646.
[18] Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. 2011. Online bipartite
matching with unknown distributions. In Proceedings of the forty-third annual
ACM symposium on Theory of computing. ACM, 587–596.
[19] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. 1990. An optimalalgorithm for on-line bipartite matching. In Proceedings of the twenty-second
annual ACM symposium on Theory of computing. ACM, 352–358.
[20] Thomas Kesselheim, Andreas Tönnis, Klaus Radke, and Berthold Vöcking. 2014.
Primal beats dual on online packing LPs in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 303–312.
[21] Meghna Lowalekar, Pradeep Varakantham, and Patrick Jaillet. 2020. Competitive
Ratios for Online Multi-capacity Ridesharing. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 771–779.
[22] Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random
arrivals: an approach based on strongly factor-revealing lps. In Proceedings of theforty-third annual ACM symposium on Theory of computing. 597–606.
[23] Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. 2012. Online
stochastic matching: Online actions based on offline statistics. Mathematics ofOperations Research 37, 4 (2012), 559–573.
[24] Aranyak Mehta and Debmalya Panigrahi. 2012. Online matching with stochastic
rewards. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science.
IEEE, 728–737.
[25] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. 2007. Adwords
and generalized online matching. Journal of the ACM (JACM) 54, 5 (2007), 22.

988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043

985
986

987

9

1044