Deterministic min-cost matching with delays

DOI10.1007/978-3-030-04693-4_2zbMath1444.68296arXiv1806.03708OpenAlexW2962989976WikidataQ126406255 ScholiaQ126406255MaRDI QIDQ5916084

Yossi Azar, Amit Jacob Fanani

Publication date: 15 January 2019

Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

competitive analysisonline algorithmbipartite matchingdelayed servicemin-cost matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Caching with Time Windows and Delays ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Competitive analysis for two variants of online metric matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• A match in time saves nine: deterministic online matching with delays
• A primal-dual online deterministic algorithm for matching with delays
• Online matching on a line
• The Online Metric Matching Problem for Doubling Metrics
• A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line
• Randomized online algorithms for minimum metric bipartite matching
• On a Greedy Heuristic for Complete Matching
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
• Online Weighted Matching
• Online service with delay
• Min-Cost Bipartite Perfect Matching with Delays
• Minimum Cost Perfect Matching with Delays for Two Sources
• Paths, Trees, and Flowers
• Online matching: haste makes waste!
• Approximation and Online Algorithms

This page was built for publication: Deterministic min-cost matching with delays