Document Open Access Logo

Permutation Strikes Back: The Power of Recourse in Online Metric Matching

Authors Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.40.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Varun Gupta
  • University of Chicago, IL, USA
Ravishankar Krishnaswamy
  • Microsoft Research India, Bangalore, India
Sai Sandeep
  • Carnegie Mellon University, Pittsburgh, PA, USA

Cite As Get BibTex

Varun Gupta, Ravishankar Krishnaswamy, and Sai Sandeep. Permutation Strikes Back: The Power of Recourse in Online Metric Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.40

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithms
  • bipartite matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Antonios Antoniadis, Carsten Fischer, and Andreas Tönnis. A collection of lower bounds for online matching on the line. In Latin American Symposium on Theoretical Informatics, pages 52-65. Springer, 2018. Google Scholar
  2. Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-cost bipartite perfect matching with delays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  3. Yossi Azar and Amit Jacob Fanani. Deterministic min-cost matching with delays. In International Workshop on Approximation and Online Algorithms, pages 21-35. Springer, 2018. Google Scholar
  4. Nikhil Bansal, Niv Buchbinder, Anupam Gupta, and Joseph Seffi Naor. An O(log²k)-competitive algorithm for metric bipartite matching. In European Symposium on Algorithms, pages 522-533. Springer, 2007. Google Scholar
  5. Marcin Bienkowski, Artur Kraska, and Paweł Schmidt. A match in time saves nine: Deterministic online matching with delays. In International Workshop on Approximation and Online Algorithms, pages 132-146. Springer, 2017. Google Scholar
  6. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. New algorithms, better bounds, and a novel model for online stochastic matching. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  7. Nikhil R Devanur, Balasubramanian Sivan, and Yossi Azar. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 388-404. ACM, 2012. Google Scholar
  8. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 333-344. ACM, 2016. Google Scholar
  9. Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, and David Wajc. Fully-dynamic bin packing with little repacking. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 51:1-51:24, 2018. Google Scholar
  10. Bernhard Fuchs, Winfried Hochstättler, and Walter Kern. Online matching on a line. Theoretical Computer Science, 332(1-3):251-264, 2005. Google Scholar
  11. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 982-991. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  12. Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. Stochastic online metric matching. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pages 67:1-67:14, 2019. Google Scholar
  13. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 537-550, 2017. Google Scholar
  14. Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 468-479, 2014. Google Scholar
  15. Anupam Gupta and Kevin Lewi. The online metric matching problem for doubling metrics. In International Colloquium on Automata, Languages, and Programming, pages 424-435. Springer, 2012. Google Scholar
  16. Varun Gupta, Ravishankar Krishnaswamy, and Sai Sandeep. PERMUTATION strikes back: The power of recourse in online metric matching. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.12778.
  17. Bala Kalyanasundaram and Kirk Pruhs. Online weighted matching. J. Algorithms, 14(3):478-488, 1993. URL: https://doi.org/10.1006/jagm.1993.1026.
  18. Samir Khuller, Stephen G Mitchell, and Vijay V Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. Theoretical Computer Science, 127(2):255-267, 1994. Google Scholar
  19. Elias Koutsoupias and Akash Nanavati. The online matching problem on a line. In International Workshop on Approximation and Online Algorithms, pages 179-191. Springer, 2003. Google Scholar
  20. Jannik Matuschke, Ulrike Schmidt-Kraepelin, and José Verschae. Maintaining perfect matchings at low cost. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pages 82:1-82:14, 2019. Google Scholar
  21. Nicole Megow and Lukas Nölke. Online minimum cost matching on the line with recourse. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.03107.
  22. Adam Meyerson, Akash Nanavati, and Laura Poplawski. Randomized online algorithms for minimum metric bipartite matching. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 954-959. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  23. Krati Nayyar and Sharath Raghvendra. An input sensitive online algorithm for the metric bipartite matching problem. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 505-515. IEEE, 2017. Google Scholar
  24. Sharath Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  25. Sharath Raghvendra. Optimal analysis of an online algorithm for the bipartite matching problem on a line. In 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pages 67:1-67:14, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact