Back to Search
Start Over
Online Algorithms for Maximum Cardinality Matching with Edge Arrivals.
- Source :
- Algorithmica; May2019, Vol. 81 Issue 5, p1781-1799, 19p
- Publication Year :
- 2019
-
Abstract
- In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in an arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1 2 -competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5 9 -competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2 3 + 1 / ϕ 2 ≈ 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, while this result slightly falls short of the currently best 1 1 + ln 2 ≈ 0.5906 bound by Epstein et al. (Inf Comput 259(1):31–40, 2018), it holds even for an easier model in which vertices along with their adjacent edges arrive online. As a result, we improve on the currently best upper bound of 0.6252 for the latter model, due to Wang and Wong (in: Proceedings of the 42nd ICALP, 2015). [ABSTRACT FROM AUTHOR]
- Subjects :
- EDGES (Geometry)
ONLINE algorithms
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 81
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 135892183
- Full Text :
- https://doi.org/10.1007/s00453-018-0505-7