Constraint satisfaction problems parameterized above or below tight bounds: A survey

Gregory Gutin*, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingBidrag til bog/antologiForskningpeer review

Resumé

We consider constraint satisfaction problems parameterized above or below tight bounds. One example is MaxSat parameterized above m/2: given a CNF formula F with m clauses, decide whether there is a truth assignment that satisfies at least m/2+k clauses, where k is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over F in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least W/2+k, where W is the total weight of all equations), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (given a CNF formula F with m clauses in which each clause has at most r literals, decide whether there is a truth assignment satisfying at least ∑ m i=1 (1-2 r i clauses, where k is the parameter, r i is the number of literals in Clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.

OriginalsprogEngelsk
TitelThe Multivariate Algorithmic Revolution and Beyond : Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday
Vol/bind7370
ForlagSpringer
Publikationsdato2012
Sider257-286
ISBN (Trykt)9783642308901
ISBN (Elektronisk)978-3-642-30891-8
DOI
StatusUdgivet - 2012
Udgivet eksterntJa
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind7370
ISSN0302-9743

Fingeraftryk

Constraint Satisfaction Problem
Assignment
Parameterized Algorithms
System of Linear Equations
Permutation
kernel
Polynomial
Truth

Citer dette

Gutin, G., & Yeo, A. (2012). Constraint satisfaction problems parameterized above or below tight bounds: A survey. I The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday (Bind 7370, s. 257-286). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind. 7370 https://doi.org/10.1007/978-3-642-30891-8_14
Gutin, Gregory ; Yeo, Anders. / Constraint satisfaction problems parameterized above or below tight bounds : A survey. The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Bind 7370 Springer, 2012. s. 257-286 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 7370).
@inbook{cbadb945d7634124882ac35dbf531656,
title = "Constraint satisfaction problems parameterized above or below tight bounds: A survey",
abstract = "We consider constraint satisfaction problems parameterized above or below tight bounds. One example is MaxSat parameterized above m/2: given a CNF formula F with m clauses, decide whether there is a truth assignment that satisfies at least m/2+k clauses, where k is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over F in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least W/2+k, where W is the total weight of all equations), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (given a CNF formula F with m clauses in which each clause has at most r literals, decide whether there is a truth assignment satisfying at least ∑ m i=1 (1-2 r i clauses, where k is the parameter, r i is the number of literals in Clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.",
author = "Gregory Gutin and Anders Yeo",
year = "2012",
doi = "10.1007/978-3-642-30891-8_14",
language = "English",
isbn = "9783642308901",
volume = "7370",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "257--286",
booktitle = "The Multivariate Algorithmic Revolution and Beyond",
address = "Germany",

}

Gutin, G & Yeo, A 2012, Constraint satisfaction problems parameterized above or below tight bounds: A survey. i The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. bind 7370, Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), bind 7370, s. 257-286. https://doi.org/10.1007/978-3-642-30891-8_14

Constraint satisfaction problems parameterized above or below tight bounds : A survey. / Gutin, Gregory; Yeo, Anders.

The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Bind 7370 Springer, 2012. s. 257-286 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 7370).

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingBidrag til bog/antologiForskningpeer review

TY - CHAP

T1 - Constraint satisfaction problems parameterized above or below tight bounds

T2 - A survey

AU - Gutin, Gregory

AU - Yeo, Anders

PY - 2012

Y1 - 2012

N2 - We consider constraint satisfaction problems parameterized above or below tight bounds. One example is MaxSat parameterized above m/2: given a CNF formula F with m clauses, decide whether there is a truth assignment that satisfies at least m/2+k clauses, where k is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over F in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least W/2+k, where W is the total weight of all equations), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (given a CNF formula F with m clauses in which each clause has at most r literals, decide whether there is a truth assignment satisfying at least ∑ m i=1 (1-2 r i clauses, where k is the parameter, r i is the number of literals in Clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.

AB - We consider constraint satisfaction problems parameterized above or below tight bounds. One example is MaxSat parameterized above m/2: given a CNF formula F with m clauses, decide whether there is a truth assignment that satisfies at least m/2+k clauses, where k is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over F in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least W/2+k, where W is the total weight of all equations), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (given a CNF formula F with m clauses in which each clause has at most r literals, decide whether there is a truth assignment satisfying at least ∑ m i=1 (1-2 r i clauses, where k is the parameter, r i is the number of literals in Clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.

U2 - 10.1007/978-3-642-30891-8_14

DO - 10.1007/978-3-642-30891-8_14

M3 - Book chapter

AN - SCOPUS:84864135167

SN - 9783642308901

VL - 7370

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 257

EP - 286

BT - The Multivariate Algorithmic Revolution and Beyond

PB - Springer

ER -

Gutin G, Yeo A. Constraint satisfaction problems parameterized above or below tight bounds: A survey. I The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Bind 7370. Springer. 2012. s. 257-286. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 7370). https://doi.org/10.1007/978-3-642-30891-8_14