Ashlagi, Itai ;
Azar, Yossi ;
Charikar, Moses ;
Chiplunkar, Ashish ;
Geri, Ofir ;
Kaplan, Haim ;
Makhijani, Rahul ;
Wang, Yuyi ;
Wattenhofer, Roger
MinCost Bipartite Perfect Matching with Delays
Abstract
In the mincost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances between matched pairs of requests (the connection cost) and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural tradeoff between minimizing the distances and the cost of waiting for better matches. This tradeoff appears in many reallife scenarios, notably, ridesharing platforms. MBPMD is related to its nonbipartite variant, mincost perfect matching with delays (MPMD), in which each request can be matched to any other request. MPMD was introduced by Emek et al. (STOC'16), who showed an O(log^2(n)+log(Delta))competitive randomized algorithm on npoint metric spaces with aspect ratio Delta.
Our contribution is threefold. First, we present a new lower bound construction for MPMD and MBPMD. We get a lower bound of Omega(sqrt(log(n)/log(log(n)))) on the competitive ratio of any randomized algorithm for MBPMD. For MPMD, we improve the lower bound from Omega(sqrt(log(n))) (shown by Azar et al., SODA'17) to Omega(log(n)/log(log(n))), thus, almost matching their upper bound of O(log(n)). Second, we adapt the algorithm of Emek et al. to the bipartite case, and provide a simplified analysis that improves the competitive ratio to O(log(n)). The key ingredient of the algorithm is an O(h)competitive randomized algorithm for MBPMD on weighted trees of height h. Third, we provide an O(h)competitive deterministic algorithm for MBPMD on weighted trees of height h. This algorithm is obtained by adapting the algorithm for MPMD by Azar et al. to the apparently more complicated bipartite setting.
BibTeX  Entry
@InProceedings{ashlagi_et_al:LIPIcs:2017:7550,
author = {Itai Ashlagi and Yossi Azar and Moses Charikar and Ashish Chiplunkar and Ofir Geri and Haim Kaplan and Rahul Makhijani and Yuyi Wang and Roger Wattenhofer},
title = {{MinCost Bipartite Perfect Matching with Delays}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {1:11:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7550},
URN = {urn:nbn:de:0030drops75509},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.1},
annote = {Keywords: online algorithms with delayed service, bipartite matching, competitive analysis}
}
11.08.2017
Keywords: 

online algorithms with delayed service, bipartite matching, competitive analysis 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 