Competitive analysis for two variants of online metric matching problem

DOI10.1142/S1793830921501561OpenAlexW3072599312MaRDI QIDQ5025166

Toshiya Itoh, Shuichi Miyazaki, Makoto Satake

Publication date: 1 February 2022

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

competitive analysisonline algorithmonline facility assignment problemonline metric matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Online bottleneck semi-matching ⋮ Online bottleneck matching on a line ⋮ Online semi-matching problem with two heterogeneous sensors in a metric space

Cites Work

• Unnamed Item
• On-line algorithms for weighted bipartite matching and stable marriages
• 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
• A collection of lower bounds for online matching on the line
• The Online Metric Matching Problem for Doubling Metrics
• Bayesian Mechanism Design
• A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Randomized online algorithms for minimum metric bipartite 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
• Min-Cost Bipartite Perfect Matching with Delays
• Impatient Online Matching
• Minimum Cost Perfect Matching with Delays for Two Sources
• Online matching: haste makes waste!
• Approximation and Online Algorithms
• Deterministic min-cost matching with delays
• Online facility assignment

This page was built for publication: Competitive analysis for two variants of online metric matching problem