Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543507 | Discrete Optimization | 2016 | 28 Pages |
Abstract
Our main theorems prove that for the (bipartite) Stable Marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite Stable Roommates instances, case (2) yields an NP-hard but (under some cardinality assumptions) 2-approximable problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Ágnes Cseh, David F. Manlove,