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

on-line deterministic algorithmrandomizationstable marriageunstable pairsweighted bipartite matching

Mathematics Subject Classification ID

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

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

(13)

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

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)