Randomized algorithms for the on-line minimum matching problem on euclidean space

DOI10.1080/00207169508804431zbMATH Open0847.68051OpenAlexW2019170215MaRDI QIDQ4876378FDOQ4876378

Authors: Ying Teh Tsai, Yunn Yen Chen, Chuan Yi Tang 

Publication date: 7 October 1996

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169508804431

Recommendations

• A randomized algorithm for the on-line weighted bipartite matching problem
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• A robust and optimal online algorithm for minimum metric bipartite matching
• A partitioning algorithm for minimum weighted Euclidean matching
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

zbMATH Keywords

competitive analysisminimum matching problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Online Weighted Matching
• A competitive 2-server algorithm
• The average-case analysis of some on-line algorithms for bin packing
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• A stochastic model of bin-packing
• Average-case analysis of the modified harmonic algorithm
• An upper bound for the average length of the euclidean minimum spanning tree
• Title not available (Why is that?)

Cited In (2)

• Online minimum matching with uniform metric and random arrivals
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory

This page was built for publication: Randomized algorithms for the on-line minimum matching problem on euclidean space

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