An LP-designed algorithm for constraint satisfaction

Autor:	Alex Scott, Gregory B. Sorkin
Rok vydání:	2016
Předmět:	Combinatorics Complexity of constraint satisfaction TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Backtracking AC-3 algorithm Constraint satisfaction dual problem Constraint logic programming Local consistency Constraint satisfaction Algorithm Constraint satisfaction problem Mathematics
Zdroj:	Lecture Notes in Computer Science ISBN: 9783540388753 ESA Scopus-Elsevier
Popis:	The class Max (r, 2)-CSP consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an (O) over tilde (r(19m/100))-time algorithm. It is the fastest algorithm for most problems in the class (including Max Cut and Max 2-Sat), and in combination with "Generalized CSPs" introduced in a companion paper, also allows counting, sampling; and the solution of problems like Max Bisection that escape the usual CSP framework. Linear programming is key to the design as well as the analysis of the algorithm.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2ac7269533b17708cd0129263497ab0c https://ora.ox.ac.uk/objects/uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb9 Zobrazit plný text záznamu