Polynomial time algorithm for an optimal stable assignment with multiple partners

DOI10.1016/j.tcs.2007.02.050zbMath1149.90087MaRDI 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

90B80: Discrete location and assignment

Related Items

Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings, Affinely representable lattices, stable matchings, and choice functions, Affinely representable lattices, stable matchings, and choice functions, A unified approach to finding good stable matchings in the hospitals/residents setting, Rotations in the stable \(b\)-matching problem, The stable \(b\)-matching polytope revisited, Understanding the generalized median stable matchings, Faster algorithms for stable allocation problems, On the set of many-to-one strongly stable fractional matchings, Three-sided matching problem with mixed preferences, Blockers and antiblockers 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), Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem, 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