Hard variants of stable marriage.
From MaRDI portal
Publication:1605313
DOI10.1016/S0304-3975(01)00206-7zbMath1050.68171OpenAlexW2059209074MaRDI QIDQ1605313
Yasufumi Morita, Robert W. Irving, Shuichi Miyazaki, Kazuo Iwama, David F. Manlove
Publication date: 15 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00206-7
Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (74)
The structure of stable marriage with indifference ⋮ Satisfied two-sided matching: a method considering elation and disappointment of agents ⋮ COALITION FORMATION GAMES: A SURVEY ⋮ Randomized approximation of the stable marriage problem ⋮ Testing substitutability of weak preferences ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Constrained stable marriage with free edges or few blocking pairs ⋮ Mixed-integer formulations for the capacitated rank pricing problem with envy ⋮ Review of the theory of stable matchings and contract systems ⋮ Distance on matchings: An axiomatic approach ⋮ Solving stable matching problems using answer set programming ⋮ Stable marriage with groups of similar agents ⋮ Robust and approximately stable marriages under partial information ⋮ Hardness and approximation results for some variants of stable marriage problem ⋮ Improved approximation algorithms for two variants of the stable marriage problem with ties ⋮ Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas ⋮ Cutoff stability under distributional constraints with an application to summer internship matching ⋮ Pareto stability in two-sided many-to-many matching with weak preferences ⋮ Algorithms and complexity of strongly stable non-crossing matchings ⋮ On the approximability of the stable matching problem with ties of size two ⋮ A simple matching domain with indifferences and a master list ⋮ Marriage market with indifferences: a linear programming approach ⋮ Locally Stable Marriage with Strict Preferences ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Parameterized algorithms for stable matching with ties and incomplete lists ⋮ Three-sided stable matchings with cyclic preferences ⋮ Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ Approximability results for stable marriage problems with ties. ⋮ Two algorithms for the student-project allocation problem ⋮ Better and Simpler Approximation Algorithms for the Stable Marriage Problem ⋮ A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem ⋮ The stable tournament problem: matching sports schedules with preferences ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Linear time local approximation algorithm for maximum stable marriage ⋮ Local search approaches in stable matching problems ⋮ Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists ⋮ Faster and simpler approximation of stable matchings ⋮ Mathematical models for stable matching problems with ties and incomplete lists ⋮ Stable fractional matchings ⋮ Bribery and Control in Stable Marriage ⋮ Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects ⋮ Stable marriage with general preferences ⋮ Matching with indifferences: a comparison of algorithms in the context of course allocation ⋮ A 25/17-approximation algorithm for the stable marriage problem with one-sided ties ⋮ Size versus stability in the marriage problem ⋮ Deferred acceptance algorithms: history, theory, practice, and open questions ⋮ Better and simpler approximation algorithms for the stable marriage problem ⋮ Efficient assignment respecting priorities ⋮ The college admissions problem with lower and common quotas ⋮ Unnamed Item ⋮ Size Versus Stability in the Marriage Problem ⋮ Improving solution times for stable matching problems through preprocessing ⋮ On the complexity of exchange-stable roommates ⋮ Complexity of finding Pareto-efficient allocations of highest welfare ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ An efficient implementation of the Gale and Shapley “propose-and-reject” algorithm ⋮ The stable marriage problem with master preference lists ⋮ Balanced stable marriage: how close is close enough? ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Super-stability in the student-project allocation problem with ties ⋮ Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem ⋮ The Stable Roommates Problem with Short Lists ⋮ Stable marriage with ties and bounded length preference lists ⋮ Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems ⋮ Borda-induced hedonic games with friends, enemies, and neutral players ⋮ Stable matching with uncertain pairwise preferences ⋮ The stable marriage problem with ties and restricted edges ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters ⋮ Hard variants of stable marriage. ⋮ A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some remarks on the stable matching problem
- A new fixed point approach for stable networks and stable marriages
- Stable marriage and indifference
- Hard variants of stable marriage.
- Minimum Edge Dominating Sets
- NP-complete stable matching problems
- An efficient algorithm for the “stable roommates” problem
- Three Fast Algorithms for Four Problems in Stable Marriage
- Edge Dominating Sets in Graphs
- College Admissions and the Stability of Marriage
This page was built for publication: Hard variants of stable marriage.
