Polynomial time algorithm for an optimal stable assignment with multiple partners

DOI10.1016/j.tcs.2007.02.050zbMath1149.90087OpenAlexW2086456639MaRDI QIDQ2373720

Varun S. Malhotra, Vipul Bansal, Aseem Agrawal

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.050

zbMATH Keywords

substitutesoptimal assignmentstable marriagemultiple partnersdis-satisfaction scoremeta-rotation

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Related Items (16)

Blockers and antiblockers of stable matchings ⋮ Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings ⋮ Cycles to compute the full set of many-to-many stable matchings ⋮ Stable allocations and partially ordered sets ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Understanding the generalized median stable matchings ⋮ Faster algorithms for stable allocation problems ⋮ A unified approach to finding good stable matchings in the hospitals/residents setting ⋮ Rotations in the stable \(b\)-matching problem ⋮ On the set of many-to-one strongly stable fractional matchings ⋮ Affinely representable lattices, stable matchings, and choice functions ⋮ The stable \(b\)-matching polytope revisited ⋮ Affinely representable lattices, stable matchings, and choice functions ⋮ Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem ⋮ Three-sided matching problem with mixed preferences ⋮ Finding a minimum-regret many-to-many Stable Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Some remarks on the stable matching problem
• An algorithm to compute the full set of many-to-many stable matchings.
• A class of multipartner matching markets with a strong lattice structure
• The lattice structure of the set of stable outcomes of the multiple partners assignment game
• Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry)
• Stability and Polarization of Interests in Job Matching
• The Complexity of Counting Stable Marriages
• The Complexity of Enumeration and Reliability Problems
• Selected Applications of Minimum Cuts in Networks
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• A Selection Problem of Shared Fixed Costs and Network Flows
• College Admissions and the Stability of Marriage
• On preferences over subsets and the lattice structure of stable matchings

This page was built for publication: Polynomial time algorithm for an optimal stable assignment with multiple partners