Online Maximum Matching with Recourse

Authors Spyros Angelopoulos , Christoph Dürr , Shendan Jin



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.8.pdf
  • Filesize: 463 kB
  • 15 pages

Document Identifiers

Author Details

Spyros Angelopoulos
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, F-75252 Paris, France
Christoph Dürr
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, F-75252 Paris, France
Shendan Jin
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, F-75252 Paris, France

Cite AsGet BibTex

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.8

Abstract

We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter k. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most k such actions per edge take place, where k is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [Avitabile et al., 2013], whereas the special case k=2 was studied by Boyar et al. [Boyar et al., 2017]. In the first part of this paper, we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [Avitabile et al., 2013], by exploiting the structure of the matching problem. In addition, we extend the result of [Boyar et al., 2017] and show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call L-Greedy, and we show that for small values of k it outperforms the algorithm of [Avitabile et al., 2013]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k-1) exists, improving upon the lower bound of 1+1/k shown in [Avitabile et al., 2013]. The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of L-Greedy and AMP carry through in this model; moreover we show a lower bound of (k^2-3k+6)/(k^2-4k+7) for all even k >= 4. For k in {2,3}, the competitive ratio is 3/2.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Online algorithms
Keywords
  • Competitive ratio
  • maximum cardinality matching
  • recourse

Metrics

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

References

  1. Tess Avitabile, Claire Mathieu, and Laura H. Parkinson. Online constrained optimization with recourse. Information Processing Letters, 113(3):81-86, 2013. Google Scholar
  2. Aaron Bernstein, Jacob Holm, and Eva Rotenberg. Online bipartite matching with amortized replacements. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 947-959. SIAM, 2018. Google Scholar
  3. Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen. Relaxing the irrevocability requirement for online graph algorithms. In Proceedings of the 15th Workshop on Algorithms and Data Structures, (WADS), pages 217-228. Springer, 2017. Google Scholar
  4. Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Online algorithms for maximum cardinality matching with edge arrivals. In Proceedings of the 25th Annual European Symposium on Algorithms, (ESA), Vienna, Austria, pages 22:1-22:14, 2017. Google Scholar
  5. Ashish Chiplunkar, Sumedh Tirodkar, and Sundar Vishwanathan. On randomized algorithms for matching in the online preemptive model. In Proceedings of the 23rd Annual European Symposium on Algorithms, (ESA), pages 325-336. Springer, 2015. Google Scholar
  6. Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. Improved bounds for online preemptive matching. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, (STACS), pages 389-399, 2013. Google Scholar
  7. 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
  8. Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: maintaining a constant-competitive steiner tree online. SIAM Journal on Computing, 45(1):1-28, 2016. Google Scholar
  9. Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), Portland, Oregon, USA, pages 455-467, 2014. Google Scholar
  10. Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 468-479, 2014. Google Scholar
  11. Xin Han and Kazuhisa Makino. Online minimization knapsack problem. In Proceedings of the 7th International Workshop on Approximation and Online Algorithms, (WAOA), pages 182-193. Springer, 2009. Google Scholar
  12. Kazuo Iwama and Shiro Taketomi. Removable online knapsack problems. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming, (ICALP), pages 293-305, 2002. Google Scholar
  13. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, (STOC), pages 352-358. ACM, 1990. Google Scholar
  14. Andrew McGregor. Finding graph matchings in data streams. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, (APPROX-RANDOM), pages 170-181. Springer, 2005. Google Scholar
  15. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM Journal on Computing, 45(3):859-880, 2016. Google Scholar
  16. Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265-368, 2013. Google Scholar
  17. C.L. Siegel. Topics in Complex Function Theory, Vol. 1: Elliptic Functions and Uniformization Theory. New York: Wiley, 1988. Google Scholar
  18. Ashwinkumar Badanidiyuru Varadaraja. Buyback problem-approximate matroid intersection with cancellation costs. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 379-390. Springer, 2011. 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