Competitive analysis for two variants of online metric matching problem

DOI10.1142/S1793830921501561OpenAlexW3072599312MaRDI QIDQ5025166FDOQ5025166

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

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

zbMATH Keywords

competitive analysisonline algorithmonline facility assignment problemonline metric matching

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)