Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays

DOI10.1137/1.9781611974782.67zbMath1409.68338arXiv1610.05155OpenAlexW4237102200MaRDI QIDQ4575807

Haim Kaplan, Ashish Chiplunkar, Yossi Azar

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (8)

Minimum Cost Perfect Matching with Delays for Two Sources ⋮ Minimum cost perfect matching with delays for two sources ⋮ Caching with Time Windows and Delays ⋮ Unnamed Item ⋮ Min-Cost Bipartite Perfect Matching with Delays ⋮ Deterministic min-cost matching with delays ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Impatient Online Matching

This page was built for publication: Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays