טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentShapiro Yaacov
SubjectMinimum Cost Perfect Matching with Delays for Two Sources
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Yuval Emek


Abstract

A version of the online min-cost perfect matching with delays (MPMD) problem recently introduced by Emek et al (STOC 2016) is studied. In this problem, requests arrive in a continuous time online fashion and should be matched to each other by the online algorithm. Each request emerges from one out of n sources, with metric inter-source distances. The algorithm is allowed to delay the matching of requests, but with a cost: when matching two requests, it pays the distance between their respective sources and the time each request has waited from its arrival until it was matched. This entails a new kind of dilemma: should the algorithm wait for new requests to arrive, allowing for (possibly) better matches, or should it match as soon as possible, thus avoiding the additional time cost? In this thesis, the special case of n = 2 sources that captures the essence of the match-or-wait challenge (cf. rent-or-buy) is considered. It turns out that even for this degenerate metric space, the problem is far from trivial. The results presented in this thesis include a deterministic 3-competitive online algorithm for the MPMD problem on two sources and a proof that no deterministic online algorithm can have competitive ratio smaller than 3.


This thesis is based on a paper with the same title that is currently under submission.