Max-Sur-CSP on Two Elements
2012 (English)In: Principles and Practice of Constraint Programming 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer Berlin Heidelberg , 2012, 38-54 p.Chapter in book (Refereed)
Max-Sur-CSP is the following optimisation problem: given a set of constraints, find a surjective mapping of the variables to domain values that satisfies as many of the constraints as possible. Many natural problems, e.g. Minimum k-Cut (which has many different applications in a variety of fields) and Minimum Distance (which is an important problem in coding theory), can be expressed as Max-Sur-CSPs. We study Max-Sur-CSP on the two-element domain and determine the computational complexity for all constraint languages (families of allowed constraints). Our results show that the problem is solvable in polynomial time if the constraint language belongs to one of three classes, and NP-hard otherwise. An important part of our proof is a polynomial-time algorithm for enumerating all near-optimal solutions to a generalised minimum cut problem. This algorithm may be of independent interest.
Place, publisher, year, edition, pages
Springer Berlin Heidelberg , 2012. 38-54 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 7514
IdentifiersURN: urn:nbn:se:liu:diva-79515DOI: 10.1007/978-3-642-33558-7_6ISBN: 978-3-642-33557-0 (print)ISBN: 978-3-642-33558-7 (online)OAI: oai:DiVA.org:liu-79515DiVA: diva2:543175
18th International Conference on Principles and Practice of Constraint Programming (CP-2012), 8-12 October, Québec City, Canada