Faster algorithms for stable allocation problems
From MaRDI portal
Publication:1959735
DOI10.1007/s00453-010-9416-yzbMath1209.68361OpenAlexW2058018786MaRDI 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
Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (12)
Blockers and antiblockers of stable matchings ⋮ Improved algorithmic results for unsplittable stable allocation problems ⋮ Finding a Stable Allocation in Polymatroid Intersection ⋮ 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 ⋮ Stable allocations and partially ordered sets ⋮ Stable flows over time ⋮ Fractional solutions for capacitated NTU-games, with applications to stable matchings ⋮ New and simple algorithms for stable flow problems ⋮ Paths to stable allocations
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
This page was built for publication: Faster algorithms for stable allocation problems