D. Cohen
Supermodular functions and the complexity of MAX CSP
Cohen, D.; Cooper, M.; Jeavons, P.; Krokhin, A.
Abstract
In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. Using the theory of sub- and supermodular functions on finite lattice-ordered sets, we obtain the first examples of general families of efficiently solvable cases of MAX CSP for arbitrary finite domains. In addition, we provide the first dichotomy result for a special class of non-Boolean MAX CSP, by considering binary constraints given by supermodular functions on a totally ordered set. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of MAX CSP which are hard even to approximate.
Citation
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics, 149(1-3), 53-72. https://doi.org/10.1016/j.dam.2005.03.003
Journal Article Type | Article |
---|---|
Publication Date | Aug 1, 2005 |
Deposit Date | Feb 21, 2008 |
Journal | Discrete Applied Mathematics |
Print ISSN | 0166-218X |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 149 |
Issue | 1-3 |
Pages | 53-72 |
DOI | https://doi.org/10.1016/j.dam.2005.03.003 |
Keywords | Constraint satisfaction problem, Optimization, Supermodularity. |
You might also like
Topology and adjunction in promise constraint satisfaction
(2023)
Journal Article
Algebraic Approach to Promise Constraint Satisfaction
(2021)
Journal Article
Robust algorithms with polynomial loss for near-unanimity CSPs
(2019)
Journal Article
Algebraic approach to promise constraint satisfaction
(2019)
Conference Proceeding
Towards a characterization of constant-factor approximable Finite-Valued CSPs
(2018)
Journal Article