A formal theory for the complexity class associated with the stable marriage problem

DOI10.4230/LIPICS.CSL.2011.381zbMATH Open1247.68095OpenAlexW2248358623MaRDI QIDQ2915696FDOQ2915696

Authors: Dai Tri Man Lê, Yuli Ye, Stephen Cook 

Publication date: 18 September 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_2d07.html

Recommendations

• Complexity study for the robust stable marriage problem
• scientific article; zbMATH DE number 45086
• On the complexity of robust stable marriage
• Hardness and approximation results for some variants of stable marriage problem
• Approximability results for stable marriage problems with ties.
• Complexity of the sex-equal stable marriage problem
• On the decomposability of the stable marriage problem
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Stable marriage with covering constraints -- a complete computational trichotomy
• Better and simpler approximation algorithms for the stable marriage problem

zbMATH Keywords

complexity theorybounded arithmeticcomparator circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (2)

• The complexity of the comparator circuit value problem
• Stable marriage with covering constraints -- a complete computational trichotomy

This page was built for publication: A formal theory for the complexity class associated with the stable marriage problem

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