Competitive analysis for two variants of online metric matching problem

DOI10.1007/978-3-030-64843-5_33MaRDI QIDQ2692234zbMATH OpenOpenAlexFDO

Authors Toshiya Itoh, Shuichi Miyazaki, Makoto Satake

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/978-3-030-64843-5_33

zbMATH Keywords

competitive analysisonline algorithmonline matching problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• Competitive analysis for two variants of online metric matching problem
• The Online Metric Matching Problem for Doubling Metrics
• Competitive analysis for multi-objective online algorithms
• Stochastic online metric matching
• Tight competitive ratios of classic matching algorithms in the fully online model
• Online two stage k-search problem and its competitive analysis
• A robust and optimal online algorithm for minimum metric bipartite matching
• scientific article; zbMATH DE number 1232130
• A novel way to analyze competitive performance of online algorithms -- instance transformation based method
• Online (J, K)-search problem and its competitive analysis

Cited in

(8)

• Online bottleneck matching
• The Online Metric Matching Problem for Doubling Metrics
• Online bottleneck matching
• Serve or skip: the power of rejection in online bottleneck matching
• Competitive analysis for two variants of online metric matching problem
• Online facility assignment
• Online semi-matching problem with two heterogeneous sensors in a metric space
• Capacity-insensitive algorithms for online facility assignment problems on a line

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 Q2692234)