Faster algorithms for stable allocation problems

DOI10.1007/s00453-010-9416-yzbMath1209.68361MaRDI QIDQ1959735

Siddharth Munshi, Brian C. Dean

Publication date: 7 October 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9416-y

zbMATH Keywords

stable matching; stable allocation; stable marriage

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

05A05: Permutations, words, matrices

68R10: Graph theory (including graph drawing) in computer science

Related Items

Finding a Stable Allocation in Polymatroid Intersection, New and simple algorithms for stable flow problems, Review of the theory of stable matchings and contract systems, On stable flows and preflows, Marriage and Roommate, On the set of stable matchings in a bipartite graph, Improved algorithmic results for unsplittable stable allocation problems, Stable flows over time, Fractional solutions for capacitated NTU-games, with applications to stable matchings, Paths to stable allocations, Blockers and antiblockers of stable matchings, Stable allocations and partially ordered sets

Cites Work

• Unnamed Item
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• A data structure for dynamic trees
• The integral stable allocation problem on graphs
• Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry)
• Polynomial time algorithm for an optimal stable assignment with multiple partners
• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• Self-adjusting binary search trees
• A new approach to the maximum-flow problem
• Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
• Erratum: The Stable Allocation (or Ordinal Transportation) Problem
• College Admissions and the Stability of Marriage