The Library
The approximability of MAX CSP with fixedvalue constraints
Tools
Deineko, Vladimir G., Jonsson, P., Klasson, Mikael and Krokhin, Andrei. (2008) The approximability of MAX CSP with fixedvalue constraints. Association for Computing Machinery Journal, Vol.55 (No.4). ISSN 00045411
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 NPhard 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 fixedvalue constraints (i. e., constraints of the form x = a), is either solvable exactly in polynomial time or else is APXcomplete, even if the number of occurrences of variables in instances is bounded. Moreover, we present a simple description of all polynomialtime solvable cases of our problem. This description relies on the wellknown 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:  00045411  
Official Date:  September 2008  
Dates: 


Volume:  Vol.55  
Number:  No.4  
Number of Pages:  37  
Identifier:  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), 62120033421 (SRC), 20064532 (SRC), EP/C543831/1 (EPSRC)  
References:  ALIMONTI, P., AND KANN, V. 2000. Some APXcompleteness results for cubic graphs. Theoret. Comput. 

URI:  http://wrap.warwick.ac.uk/id/eprint/29330 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 