Tight competitive ratios of classic matching algorithms in the fully online model

DOI10.1137/1.9781611975482.178MaRDI QIDQ5236370zbMATH OpenOpenAlexFDO

Authors Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, Yu-Hao Zhang, Zhiyi Huang

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07903

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27) Matching models (91B68)

Abstract: Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al.~(STOC 1990) is strictly better than $0.5$-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be $(1-1/e)$-competitive. This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is $2-sqrt2approx0.585$-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art $frac11+ln2approx0.5906$ upper bound. For integral algorithms, we show a tight competitive ratio of $approx0.567$ for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018).

Recommendations

• Fully online matching
• Tighter bounds for online bipartite matching
• How to match when all vertices arrive online
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions

Cited in

(22)

• Best fit bin packing with random order revisited
• A stronger impossibility for fully online matching
• Online total bipartite matching problem
• Competitive analysis for two variants of online metric matching problem
• Tighter bounds for online bipartite matching
• Prophet matching with general arrivals
• Best fit bin packing with random order revisited
• Stochastic online metric matching
• Dynamic stochastic matching under limited time
• Fully online matching
• Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios
• How to match when all vertices arrive online
• Online matching with concave returns
• Computing maximum matchings in temporal graphs
• Edge-weighted online bipartite matching
• Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
• Robust algorithms under adversarial injections
• Online algorithm for fractional matchings with edge arrivals in graphs of maximum degree three
• Toward a better understanding of randomized greedy matching
• Online matching with high probability
• Online stochastic matching with edge arrivals
• Edge arrival online matching: the power of free disposal on acyclic graphs

This page was built for publication: Tight competitive ratios of classic matching algorithms in the fully online model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236370)