On-line algorithms for weighted bipartite matching and stable marriages

DOI10.1007/3-540-54233-7_178MaRDI QIDQ4036608zbMATH OpenFDO

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

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-54233-7_178

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: On-line algorithms for weighted bipartite matching and stable marriages

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