The Power of Greedy for Online Minimum Cost Matching on the Line Eric Balkanski Yuri Faenza and Noemie Perivier

2025-05-06 0 0 1.21MB 84 页 10玖币

侵权投诉

The Power of Greedy for Online Minimum Cost Matching

on the Line

Eric Balkanski, Yuri Faenza, and Noemie Perivier

Columbia University

In the online minimum cost matching problem, there are nservers and, at each of ntime steps,

a request arrives and must be irrevocably matched to a server that has not yet been matched,

with the goal of minimizing the sum of the distances between the matched pairs. Online minimum

cost matching is a central problem in applications such as ride-hailing platforms and food delivery

services. Despite achieving a worst-case competitive ratio that is exponential in neven on the line,

the simple greedy algorithm, which matches each request to its nearest available server, performs

very well in practice. A major question is thus to explain greedy’s strong empirical performance.

In this paper, we aim to understand the performance of greedy on the line over instances that are

at least partially random.

When both the requests and the servers are drawn uniformly and independently from [0,1],

we obtain a constant competitive ratio for greedy, which improves over the previously best-known

bound of O(√n) for greedy in this setting, and also show that this constant competitive ratio holds

in the excess supply setting where there is a linear excess of servers. In the semi-random model

where the requests are still drawn uniformly and independently but where the servers are chosen

adversarially, we show that greedy achieves an Θ(log n) competitive ratio. These results invite

further investigation about how much randomness is necessary and suﬃcient to obtain guarantees

for the greedy algorithm, on the line and beyond.

arXiv:2210.03166v3 [cs.DS] 27 Mar 2025

Contents

1 Introduction 1

1.1 Technical overview ..................................... 4

1.2 Additional related work .................................. 5

2 Preliminaries 6

3 Greedy is Constant Competitive in the Fully Random Model 8

4 Greedy is O(log n)-competitive in the Random Requests Model 13

5 Greedy is Ω(log n)-competitive in the Random request Model: Overview of the

Proof 14

5.1 Description of the instance ................................. 15

5.2 Analysis of the instance .................................. 15

5.3 The main lower bound result ............................... 19

A Extensions 25

A.1 Beyond the line ....................................... 25

A.2 Beyond the uniform assumption .............................. 27

A.3 The random servers model ................................. 28

A.4 The sublinear excess of servers regime .......................... 28

B Strategyproofness in Online Minimum Cost Matching 28

C Auxiliary Lemmas 30

D Proof of the Hybrid Lemma (Lemma 5) 31

E Missing Analysis from Section 3 42

F Missing Analysis from Section 4 45

G Hierarchical Greedy is Ω(n1/4)in the Random Requests Model 48

H Greedy is Ω(log n)-competitive 50

H.1 Preliminaries ........................................ 50

H.2 Upper bound on the cost of the optimal oﬄine matching ................ 52

H.3 Analysis of (S1, . . . , Sn). .................................. 53

H.4 Lower bound on E[cost(Hm−1)−cost(Hm)]. ....................... 57

I Missing Analysis from Section H 63

I.1 Missing analysis from Section H.1 ............................. 64

I.2 Missing analysis from Section H.3 ............................. 65

I.3 Missing analysis from Section H.4 ............................. 69

1 Introduction

Matching problems are a core area of discrete optimization. In the 90s, a seminal paper by Karp

et al. [30] introduced online bipartite maximum matching problems and showed that, in the worst-

case scenario, no deterministic algorithm can beat a simple greedy procedure, and no randomized

algorithm can beat ranking, which is a greedy procedure preceded by a random shuﬄing of the order

of the nodes. These elegant results and their natural application to online advertising spurred much

research, especially from the late 2000s on (see, e.g., [39] and the references therein for a survey).

While more complex algorithms have been devised for models other than worst-case analysis, greedy

techniques are often used as a competitive benchmark for comparisons, see, e.g., [17,34,50].

In the last few years, motivated by the surge of ride-sharing platforms, a second online matching

paradigm has received much attention: online (bipartite) minimum cost matching. In this class

of problems, one side of the market is composed of servers (sometimes called drivers) and is fully

known at time 0. Nodes from the other side, often called requests or customers, arrive one at a

time. When request iarrives, we must match it to one of the servers j, and incur a cost cij . Server

jis then removed from the list of available servers, and the procedure continues. The goal is to

minimize the total cost of the matching.

Given the motivating application to ride-sharing, it is natural to impose the condition that

both servers and requests belong to some metric space (e.g., [26,29,44,49]). Many algorithms in

this area involve non-trivial, in some cases computationally expensive, procedures like randomized

tree embeddings [40,7], iterative segmentation of the space [29] or primal-dual arguments based

on the computation of oﬄine optimal matchings at each time step [45]. Other algorithms use

randomization to bypass worst-case scenarios for deterministic algorithms [21].

The predominant objective of this line work has been to design algorithms that achieve the

strongest possible performance guarantees in terms of quality of the solution found, which is mea-

sured by an algorithm’s competitive ratio. However, there are other important considerations when

deploying systems that match individuals in real time, such as simplicity, strategyproofness, run-

ning time, and explainability. An extremely simple algorithm that is highly desirable with respect

to all these factors is the greedy algorithm, also called nearest neighbor, that matches each incoming

request to the closest available server. But does it perform well?

Somehow surprisingly, this algorithm often works very well in practice: experiments have shown

that greedy was more eﬀective than other existing algorithms in most tests and has outstanding

scalability [48]. This performance substantiates the choice of many ride-sharing platforms to actu-

ally implement greedy procedures, in combination with other techniques [8,25]. However, current

theory exhibits a mismatch with such strong computational results: if we assume that nservers

and nrequests are adversarially placed on a line, the greedy algorithm only achieves a 2n−1

competitive ratio [26,31,49]. It is therefore important to develop a theory that closes the gap with

practice and gives solid ground to the use of the greedy algorithm. This motivates the ﬁrst guiding

question of the paper.

Can we ﬁnd a theoretical justiﬁcation for the strong practical performance of the greedy

algorithm for online minimum cost matching problems?

A standard approach to the question above is to make a distributional assumption on the input.

Obviously, stronger assumptions may lead to stronger positive results – but such assumptions may

not be veriﬁed in practice. Ideally, we would like to identify the hypotheses that are necessary

to guarantee a strong performance for the greedy procedure. These results can provide important

guidance to practitioners: depending on whether or not they believe such hypothesis to be veriﬁed

by their data, they can choose to either apply the greedy algorithm or to resort to a more reﬁned

procedure. This discussion motivates the second guiding question of the paper.

What are necessary and suﬃcient assumptions to guarantee that the greedy procedure

outputs a solution whose quality is asymptotically optimal?

These questions have important implications since they aim to characterize the scenarios where a

simple greedy algorithm can be used instead of signiﬁcantly more complex algorithms for a problem

central to multiple large modern markets such as ride-sharing and food delivery.

Understanding the strong practical performance of simple algorithms has motivated a lot of

work on beyond the worst-case analysis of algorithms. Some examples include using properties

such as curvature, stability, sharpness, and smoothness to obtain improved guarantees for greedy

for submodular maximization [11,10,43,46] and diﬀerent semi-random models for analyzing k-

means for clustering [5,35], local search for the traveling salesman problem [14,33,15,6], and greedy

for online maximum matching [20,13,36,4]. In the context of online minimum cost matching,

our understanding of the performance of greedy is very limited. Despite its simplicity, greedy is

hard to analyze because a greedy match at some time step can have complex consequences on the

available servers in a diﬀerent region at a much later time step. In other words, “the state of the

system under the standard greedy algorithm is hard to keep track of analytically” [28].

As a step towards understanding the power and limits of greedy, we focus on a fundamental,

deceptively simple setting, which is in fact one of the most studied in the area: online minimum

cost matching on the line. Despite much work [1,21,42,23,37,45,32,41,19], the performance of

simple algorithms for this model are far from being understood.

We ﬁrst consider the fully random model, where the nservers and nrequests are all drawn

uniformly and independently from [0,1]. In this model, the best known bound on the competitive

ratio of greedy is a trivial O(√n) bound,1and there are more sophisticated algorithms such as

hierarchical greedy [29] and fair-bias [22] that are constant competitive in Euclidean spaces and

on the line, respectively.2Our ﬁrst main result settles the asymptotic performance of greedy

for matching on the line in the fully random model by showing that greedy achieves a constant

competitive ratio.

Theorem 1. For online matching on the line in the fully random model, the greedy algorithm

achieves a constant competitive ratio.

A main beneﬁt of greedy is that it is customer-strategyproof, meaning that the customers

arriving online have no incentive to misreport the location of their requests. We note that this

result improves the best-known competitive ratio of any mechanism that is customer-strategyproof

from O(√n) to constant for this setting (in fact, we are not aware of any non-trivial customer-

strategyproof mechanism besides greedy). We refer to Appendix Bfor a discussion and a formal

deﬁnition of customer-strategyproofness.

1There is a known Ω(√n) bound on the optimal cost (see, e.g., [49]) and the cost of any algorithm is trivially

upper bounded by n.

2Note that hierarchical greedy is constant competitive only for d= 1 or d≥3. For d= 2, Kanoria [29] shows that

an adapted version of the gravitational matching algorithm by Holden et al. [24] is constant competitive.

We show that this constant competitiveness of greedy also holds in the fully random ϵ−excess

model, for every constant ϵ∈[0,1]. This is a modiﬁcation of the fully random model where there is

a linear excess of servers, i.e., (1+ϵ)nservers. This results improves over the previously best-known

competitive ratio for greedy of O(log3n) in this setting, which was a byproduct of a result by [1].

Theorem 2. For any constant ϵ∈[0,1], greedy is constant competitive in the fully random ϵ-excess

model.

It is widely acknowledged (see, e.g., [16]) that i.i.d. instances often do not resemble “real”

instances. We next therefore consider whether strong guarantees for greedy can also be obtained in

a semi-random model. In particular, we consider a model that we call the random requests model

where the nservers are adversarially chosen and the requests are, as in the fully random model,

drawn uniformly and independently. Our next result shows that greedy is logarithmic competitive

in the random requests model.

Theorem 3. For online matching on the line in the random requests model, the greedy algorithm

achieves an O(log n)-competitive ratio.

In the model where the servers and requests are chosen adversarially but where the arrival

order is random, O(n) and Ω(n0.26) upper and lower bounds are known for the competitive ratio

of greedy [9]. Combined with this Ω(n0.26) lower bound, our result shows that the performance of

greedy improves exponentially when the locations of the requests are also random. Interestingly,

hierarchical greedy only achieves a polynomial competitive ratio in the random requests model

(see Appendix G). Our last main result shows that this competitive ratio of greedy in the random

requests model is tight.

Theorem 4. For online matching on the line in the random requests model, the greedy algorithm

achieves an Ω(log n)-competitive ratio.

Combined with Theorem 3, we obtain that greedy is Θ(log n)-competitive in the random re-

quests model. The combination of our four results give a ﬁrst partial characterization of the

scenarios in which greedy is guaranteed to perform well for online minimum cost matching. How-

ever, there remain multiple intriguing and well-motivated extensions of the two models we consider

where the performance of greedy is poorly understood and where strong competitive ratio guaran-

tees might be achievable. These extensions and their challenges are discussed in Appendix Aand

include

•more general metric spaces beyond the line, such as the unit hypercube of arbitrary dimension

dfor which we provide numerical simulations where greedy achieve a competitive ratio that

is always at most 1.4 (Appendix A.1),

•a relaxation of the uniform assumption where the requests are instead drawn i.i.d. from an

arbitrary distribution (Appendix A.2),

•the random servers model where the servers are adversarially chosen and the requests are

drawn uniformly and independently (Appendix A.3), and

•the sublinear excess supply setting where there is a sublinear excess number of servers com-

pared to the number of requests (Appendix A.4).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ThePowerofGreedyforOnlineMinimumCostMatchingontheLineEricBalkanski,YuriFaenza,andNoemiePerivierColumbiaUniversityIntheonlineminimumcostmatchingproblem,therearenserversand,ateachofntimesteps,arequestarrivesandmustbeirrevocablymatchedtoaserverthathasnotyetbeenmatched,withthegoalofminimizingthesumofthe...

展开>> 收起<<

The Power of Greedy for Online Minimum Cost Matching on the Line Eric Balkanski Yuri Faenza and Noemie Perivier.pdf

共84页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The Power of Greedy for Online Minimum Cost Matching on the Line Eric Balkanski Yuri Faenza and Noemie Perivier

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: