Competitive analysis for two variants of online metric matching problem

DOI10.1142/S1793830921501561MaRDI QIDQ5025166OpenAlexFDO

Authors 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

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

Recommendations

• Competitive analysis for two variants of online metric matching problem
• scientific article; zbMATH DE number 7236471
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• Approximation and Online Algorithms
• The Online Metric Matching Problem for Doubling Metrics

Cites work

• scientific article; zbMATH DE number 7236471 (Why is no real title available?)
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A collection of lower bounds for online matching on the line
• A match in time saves nine: deterministic online matching with delays
• A primal-dual online deterministic algorithm for matching with delays
• A robust and optimal online algorithm for minimum metric bipartite matching
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Approximation and Online Algorithms
• Impatient Online Matching
• Min-cost bipartite perfect matching with delays
• Minimum cost perfect matching with delays for two sources
• On-line algorithms for weighted bipartite matching and stable marriages
• Online Weighted Matching
• Online facility assignment
• Online matching and ad allocation
• Online matching on a line
• Online matching: haste makes waste!
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Randomized online algorithms for minimum metric bipartite matching
• The Online Metric Matching Problem for Doubling Metrics

Cited in

(7)

• Online bottleneck matching on a line
• Online bottleneck semi-matching
• Online facility assignment for general layout of servers on a line
• The Online Metric Matching Problem for Doubling Metrics
• Online semi-matching problem with two heterogeneous sensors in a metric space
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Competitive analysis for two variants of online metric matching problem

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

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