Hardness results for stable exchange problems

DOI10.1016/J.TCS.2017.01.023MaRDI QIDQ5965780zbMATH OpenOpenAlexFDO

Authors Zsuzsa Mészáros-Karkus

Publication date 16 March 2017

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

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

zbMATH Keywords

computational complexitykidney exchangestable exchangestable partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Recommendations

• Hardness results for stable exchange problems
• The cycle roommates problem: a hard case of kidney exchange
• The exchange-stable marriage problem
• On the complexity of exchange-stable roommates
• Stable matching problems with exchange restrictions

Cites work

• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5049926 (Why is no real title available?)
• Kidney Exchange
• Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
• On cores and indivisibility
• On the parameterized complexity of multiple-interval graph problems
• Stable matchings in three-sided systems with cyclic preferences
• The cycle roommates problem: a hard case of kidney exchange
• The kidney exchange problem: how hard is it to find a donor?
• The Stable Roommates Problem with Ties
• Three-Dimensional Stabl Matching Problems
• Three-dimensional stable matching with cyclic preferences
• Three-sided stable matchings with cyclic preferences
• Weak versus strong domination in a market with indivisible goods

Cited in

(8)

• The cycle roommates problem: a hard case of kidney exchange
• Randomized parameterized algorithms for the kidney exchange problem
• Tropical vertex-disjoint cycles of a vertex-colored digraph: barter exchange with multiple items per agent
• Hardness results for stable exchange problems
• Novel integer programming models for the stable kidney exchange problem
• Local stability in kidney exchange programs
• Operational research approaches and mathematical models for kidney exchange: a literature survey and empirical evaluation
• Computational complexity of the problem of choosing exchange alternatives with a limited number of indivisible resources

This page was built for publication: Hardness results for stable exchange problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5965780)