The Library

The approximability of MAX CSP with fixed-value constraints

Tools

Deineko, Vladimir G., Jonsson, P., Klasson, Mikael and Krokhin, Andrei. (2008) The approximability of MAX CSP with fixed-value constraints. Association for Computing Machinery Journal, Vol.55 (No.4). ISSN 0004-5411

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1145/1391289.1391290

Abstract

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of ( possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number ( or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this article, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i. e., constraints of the form x = a), is either solvable exactly in polynomial time or else is APX-complete, even if the number of occurrences of variables in instances is bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software

Divisions:

Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences
Faculty of Social Sciences > Warwick Business School

Library of Congress Subject Headings (LCSH):

Algorithms, Computational complexity, Approximation theory, Combinatorial optimization

Journal or Publication Title:

Association for Computing Machinery Journal

Publisher:

Association for Computing Machinery, Inc.

ISSN:

0004-5411

Official Date:

September 2008

Dates:

Date	Event
September 2008	Published

Volume:

Vol.55

Number:

No.4

Number of Pages:

Identification Number:

10.1145/1391289.1391290

Status:

Peer Reviewed

Publication Status:

Published

Access rights to Published version:

Restricted or Subscription Access

Funder:

University of Warwick. Centre for Discrete Mathematics and its Applications (DIMAP), Universitetet i Linköping. Center for Industrial Information Technology (CENIIT), Sweden. Vetenskapsrådet [Swedish Research Council], Engineering and Physical Sciences Research Council (EPSRC)

Grant number:

04.01 (CENIIT), 621-2003-3421 (SRC), 2006-4532 (SRC), EP/C543831/1 (EPSRC)

References:

ALIMONTI, P., AND KANN, V. 2000. Some APX-completeness results for cubic graphs. Theoret. Comput.
Sci. 237, 1-2, 123–134.
AUSIELLO, G., CRESZENZI, P., GAMBOSI, G., KANN, V., MARCHETTI-SPACCAMELA, A., AND PROTASI, M.
1999. Complexity and Approximation. Springer-Verlag, New York.
BAZGAN, C., AND KARPINSKI,M. 2005. On the complexity of global constraint satisfaction. In Proceedings
of the International Symposium on Algorithms and Computation (ISAAC’05). 624–633.
BERMAN, P., AND KARPINSKI, M. 2003. Improved approximation lower bounds on small occurrence
optimization. Tech. Rep. TR03-008, Electronic Colloquium on Computational Complexity (ECCC).
B¨ORNER, F., BULATOV, A., JEAVONS, P., AND KROKHIN, A. 2003. Quantified constraints: Algorithms and
complexity. In Proceedings of the Workshop on Computer Science Logic (CSL’03). Lecture Notes in
Computer Science, vol. 2803. Springer-Verlag, New York, 58–70.
BULATOV,A. 2003. Tractable conservative constraint satisfaction problems. In Proceedings of the Annual
IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 321–
330.
BULATOV, A. 2006. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J.
ACM 53, 1, 66–120.
BULATOV, A., AND DALMAU, V. 2007. Towards a dichotomy theorem for the counting constraint satisfaction
problem. Inf. Computat. 205, 5, 651–678.
BULATOV, A., JEAVONS, P., AND KROKHIN, A. 2005. Classifying complexity of constraints using finite
algebras. SIAM J. Comput. 34, 3, 720–742.
BURKARD, R., KLINZ, B., AND RUDOLF, R. 1996. Perspectives of Monge properties in optimization.
Disc. Appl. Math. 70, 95–161.
COHEN, D., COOPER, M., JEAVONS, P., AND KROKHIN, A. 2005. Supermodular functions and the complexity
of Max CSP. Disc. Appl. Math. 149, 1-3, 53–72.
CREIGNOU, N. 1995. A dichotomy theorem for maximum generalized satisfiability problems. J. Comput.
Syst. Sci. 51, 511–522.
CREIGNOU, N., KHANNA, S., AND SUDAN, M. 2001. Complexity classifications of Boolean constraint
satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications, vol. 7.
DATAR,M., FEDER, T., GIONIS, A.,MOTWANI, R., AND PANIGRAHY, R. 2003. A combinatorial algorithm
for MAX CSP. Inf. Proc. Lett. 85, 6, 307–315.
DEINEKO, V., RUDOLF, R., ANDWOEGINGER, G. 1994. A general approach to avoiding 2×2 submatrices.
Computing 52, 371–388.
ENGEBRETSEN, L. 2004. The non-approximability of non-Boolean predicates. SIAM J. Disc. Math. 18, 1,
114–129.
FEDER, T., AND VARDI,M. 1998. The computational structure of monotone monadic SNP and constraint
satisfaction: A study through Datalog and group theory. SIAM J. Comput. 28, 57–104.
FUJISHIGE, S. 2005. Submodular Functions and Optimization, 2nd ed. Annals of Discrete Mathematics,
vol. 58. Elsevier.
GUTIN, G., RAfiEY, A., YEO, A., AND TSO, M. 2006. Level of repair analysis and minimum cost homomorphisms
of graphs. Disc. Appl. Math. 154, 6, 881–889.
HAST, G. 2005. Beating a random assignment: Approximating constraint satisfaction problems. Ph.D.
dissertation Royal Institute of Technology, Stockholm, Sweden.
H°ASTAD, J. 2000. On bounded occurrence constraint satisfaction. Inf. Proc. Lett. 74, 1-2, 1–6.
H°ASTAD, J. 2001. Some optimal inapproximability results. J. ACM 48, 798–859.
H°ASTAD, J. 2005. Every 2-CSP allows nontrivial approximation. In Proceedings of the Annual ACM
Symposium on Theory of Computing (STOC’05). ACM, New York, 740–746.
HELL, P. 2003. Algorithmic aspects of graph homomorphisms. In Surveys in Combinatorics 2003,
C. Wensley, Ed. LMS Lecture Note Series, vol. 307. Cambridge University Press, Cambridge, MA,
239–276.