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)

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

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)