scientific article; zbMATH DE number 176778

MaRDI QIDQ4036608zbMATH OpenFDO

Authors Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani

Publication date 18 May 1993

zbMATH Keywords

randomizationstable marriageweighted bipartite matchingon-line deterministic algorithmunstable pairs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Online Weighted Matching
• A randomized algorithm for the on-line weighted bipartite matching problem
• Deferred on-line bipartite matching
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions

Cited in

(12)

• Randomized algorithms for the on-line minimum matching problem on euclidean space
• On the advice complexity of online bipartite matching and online stable marriage
• On the lower bound of the competitive ratio for the weighted online roommates problem
• Competitive Weighted Matching in Transversal Matroids
• A randomized algorithm for the on-line weighted bipartite matching problem
• An \(O(\log n)\)-competitive posted-price algorithm for online matching on the line
• Online Weighted Matching
• Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space
• Measuring the instability in two-sided matching procedures
• Deferred on-line bipartite matching
• Dynamic weighted matching with heterogeneous arrival and departure rates
• Online 2-stage stable matching

This page was built for publication:

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