License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.40
URN: urn:nbn:de:0030-drops-126431
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12643/
Gupta, Varun ;
Krishnaswamy, Ravishankar ;
Sandeep, Sai
Permutation Strikes Back: The Power of Recourse in Online Metric Matching
Abstract
In this paper, we study the online metric matching with recourse (OMM-Recourse) problem. Given a metric space with k servers, a sequence of clients is revealed online. A client must be matched to an available server on arrival. Unlike the classical online matching model where the match is irrevocable, the recourse model permits the algorithm to rematch existing clients upon the arrival of a new client. The goal is to maintain an online matching with a near-optimal total cost, while at the same time not rematching too many clients.
For the classical online metric matching problem without recourse, the optimal competitive ratio for deterministic algorithms is 2k-1, and the best-known randomized algorithms have competitive ratio O(log² k). For the much-studied special case of line metric, the best-known algorithms have competitive ratios of O(log k). Improving these competitive ratios (or showing lower bounds) are important open problems in this line of work.
In this paper, we show that logarithmic recourse significantly improves the quality of matchings we can maintain online. For general metrics, we show a deterministic O(log k)-competitive algorithm, with O(log k) recourse per client, an exponential improvement over the 2k-1 lower bound without recourse. For line metrics we show a deterministic 3-competitive algorithm with O(log k) amortized recourse, again improving the best-known O(log k)-competitive algorithms without recourse. The first result (general metrics) simulates a batched version of the classical algorithm for OMM called Permutation. The second result (line metric) also uses Permutation as the foundation but makes non-trivial changes to the matching to balance the competitive ratio and recourse.
Finally, we also consider the model when both clients and servers may arrive or depart dynamically, and exhibit a simple randomized O(log n)-competitive algorithm with O(log Δ) recourse, where n and Δ are the number of points and the aspect ratio of the underlying metric. We remark that no non-trivial bounds are possible in this fully-dynamic model when no recourse is allowed.
BibTeX - Entry
@InProceedings{gupta_et_al:LIPIcs:2020:12643,
author = {Varun Gupta and Ravishankar Krishnaswamy and Sai Sandeep},
title = {{Permutation Strikes Back: The Power of Recourse in Online Metric Matching}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {40:1--40:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12643},
URN = {urn:nbn:de:0030-drops-126431},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.40},
annote = {Keywords: online algorithms, bipartite matching}
}
|
Keywords: |
|
online algorithms, bipartite matching |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.08.2020 |
