Document Open Access Logo

Online Minimum Cost Matching with Recourse on the Line

Authors Nicole Megow , Lukas Nölke

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.37.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Nicole Megow
  • Department for Mathematics and Computer Science, University of Bremen, Germany
Lukas Nölke
  • Department for Mathematics and Computer Science, University of Bremen, Germany

Funding

  • Megow, Nicole: Partially supported by the German Science Foundation (DFG) under contract ME 3825/1.

Cite As Get BibTex

Nicole Megow and Lukas Nölke. Online Minimum Cost Matching with Recourse on the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.37

Abstract

In online minimum cost matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an O(1)-competitive algorithm. The best known online algorithm by Raghvendra [S. Raghvendra, 2018] achieves a competitive factor of Θ(log n). This result matches a lower bound of Ω(log n) [A. Antoniadis et al., 2018] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. 
In this work, we approach the problem in a recourse model where we allow to revoke online decisions to some extent, i.e., we allow to reassign previously matched edges. We show an O(1)-competitive algorithm for online matching on the line with amortized recourse of O(log n). This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a (1+ε)-competitive algorithm that reassigns any request at most O(ε^{-1.001}) times. This special case is interesting as the aforementioned quite general lower bound Ω(log n) holds for such instances.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Theory of computation → Online algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • min-cost matching in bipartite graphs
  • recourse
  • competitive analysis
  • online

Metrics

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

Related Versions

References

  1. S. Angelopoulos, C. Dürr, and S. Jin. Online maximum matching with recourse. In MFCS, volume 117 of LIPIcs, pages 8:1-8:15, 2018. Google Scholar
  2. A. Antoniadis, N. Barcelo, M. Nugent, K. Pruhs, and M. Scquizzato. A o(n)-competitive deterministic algorithm for online matching on a line. Algorithmica, 81(7):2917-2933, 2019. Google Scholar
  3. A. Antoniadis, C. Fischer, and A. Tönnis. A collection of lower bounds for online matching on the line. In LATIN, volume 10807 of LNCS, pages 52-65, 2018. Google Scholar
  4. T. Avitabile, C. Mathieu, and L. Parkinson. Online constrained optimization with recourse. Inf. Process. Lett., 113(3):81-86, 2013. Google Scholar
  5. N. Bansal, N. Buchbinder, A. Gupta, and J. Naor. A randomized o(log² k)-competitive algorithm for metric bipartite matching. Algorithmica, 68(2):390-403, 2014. Google Scholar
  6. A. Bernstein, J. Holm, and E. Rotenberg. Online bipartite matching with amortized o(log² n) replacements. J. ACM, 66(5):37:1-37:23, 2019. Google Scholar
  7. B. Bosek, D. Leniowski, P. Sankowski, and A. Zych. Online bipartite matching in offline time. In FOCS, pages 384-393, 2014. Google Scholar
  8. K. Chaudhuri, C. Daskalakis, R. Kleinberg, and H. Lin. Online bipartite perfect matching with augmentations. In INFOCOM, pages 1044-1052, 2009. Google Scholar
  9. R. Duan and S. Pettie. Linear-time approximation for maximum weight matching. J. ACM, 61(1):1:1-1:23, 2014. Google Scholar
  10. B. Fuchs, W. Hochstättler, and W. Kern. Online matching on a line. Theor. Comput. Sci., 332(1-3):251-264, 2005. Google Scholar
  11. M. Gairing and M. Klimm. Greedy metric minimum online matchings with random arrivals. Oper. Res. Lett., 47(2):88-91, 2019. Google Scholar
  12. E. Grove, M.-Y. Kao, P. Krishnan, and J. Vitter. Online perfect matching and mobile computing. In WADS, volume 955 of LNCS, pages 194-205, 1995. Google Scholar
  13. A. Gu, A. Gupta, and A. Kumar. The power of deferral: Maintaining a constant-competitive steiner tree online. SIAM J. Comput., 45(1):1-28, 2016. Google Scholar
  14. A. Gupta, G. Guruganesh, B. Peng, and D. Wajc. Stochastic online metric matching. In ICALP, volume 132 of LIPIcs, pages 67:1-67:14, 2019. Google Scholar
  15. A. Gupta, A. Kumar, and C. Stein. Maintaining assignments online: Matching, scheduling, and flows. In SODA, pages 468-479, 2014. Google Scholar
  16. A. Gupta and K. Lewi. The online metric matching problem for doubling metrics. In ICALP, volume 7391 of LNCS, pages 424-435, 2012. Google Scholar
  17. V. Gupta, R. Krishnaswamy, and S. Sandeep. Permutation strikes back: The power of recourse in online metric matching. Accepted to appear in APPROX-RANDOM, 2020. Google Scholar
  18. M. Imase and B. Waxman. Dynamic steiner tree problem. SIAM J. Discrete Math., 4(3):369-384, 1991. Google Scholar
  19. B. Kalyanasundaram and K. Pruhs. Online weighted matching. J. Algorithms, 14(3):478-488, 1993. Google Scholar
  20. R. Karp, U. Vazirani, and V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, pages 352-358, 1990. Google Scholar
  21. S. Khuller, S. Mitchell, and V. Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci., 127(2):255-267, 1994. Google Scholar
  22. H. W. Kuhn and B. Yaw. The hungarian method for the assignment problem. Naval Res. Logist. Quart, pages 83-97, 1955. Google Scholar
  23. J. Lacki, J. Oćwieja, M. Pilipczuk, P. Sankowski, and A. Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the steiner tree. In STOC, pages 11-20, 2015. Google Scholar
  24. J. Matuschke, U. Schmidt-Kraepelin, and J. Verschae. Maintaining perfect matchings at low cost. In ICALP, volume 132 of LIPIcs, pages 82:1-82:14, 2019. Google Scholar
  25. N. Megow, M. Skutella, J. Verschae, and A. Wiese. The power of recourse for online MST and TSP. SIAM J. Comput., 45(3):859-880, 2016. Google Scholar
  26. A. Mehta. Online matching and ad allocation. Found. Trends Theor. Comput. Sci., 8(4):265-368, 2013. Google Scholar
  27. K. Nayyar and S. Raghvendra. An input sensitive online algorithm for the metric bipartite matching problem. In FOCS, pages 505-515, 2017. Google Scholar
  28. S. Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In APPROX-RANDOM, volume 60 of LIPIcs, pages 18:1-18:16, 2016. Google Scholar
  29. S. Raghvendra. Optimal analysis of an online algorithm for the bipartite matching problem on a line. In SoCG, volume 99 of LIPIcs, pages 67:1-67:14, 2018. Google Scholar
  30. Yongho Shin, Kangsan Kim, Seungmin Lee, and Hyung-Chan An. Online graph matching problems with a worst-case reassignment budget. CoRR, abs/2003.05175, 2020. URL: http://arxiv.org/abs/2003.05175.
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