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

DOI10.1080/00207169508804431MaRDI QIDQ4876378zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

competitive analysisminimum matching problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A randomized algorithm for the on-line weighted bipartite matching problem
• A randomized O(^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

Cites work

• scientific article; zbMATH DE number 176778 (Why is no real title available?)
• A competitive 2-server algorithm
• A stochastic model of bin-packing
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• An upper bound for the average length of the euclidean minimum spanning tree
• Average-case analysis of the modified harmonic algorithm
• Online Weighted Matching
• The average-case analysis of some on-line algorithms for bin packing

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)