TY - GEN

T1 - Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints

AU - Chen, Xue

AU - Zhou, Yuan

N1 - Funding Information:
This work was supported by NSF Grant CCF-1526952.
Publisher Copyright:
Copyright © by SIAM.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Given a constraint satisfaction problem (CSP) on n variables, x1; x2; : : : ; xn 2 ( ±1), andmconstraints, a global cardinality constraint has the form of Pn i=1 xi = (1 2p)n, where p ∈ ((1); 1 (1)) and pn is an integer. Let AV G be the expected number of constraints satisfied by randomly choosing an assignment to x1; x2; : : : ; xn, complying with the global cardinality constraint. The CSP above average with the global cardinality constraint problem asks whether there is an assignment (complying with the cardinality constraint) that satisfies more than (AV G + t) constraints, where t is an input parameter. In this paper, we present an algorithm that finds a valid assignment satisfying more than (AV G + t) constraints (if there exists one) in time (2O(t2) + nO(d)). Therefore, the CSP above average with the global cardinality constraint problem is fixed-parameter tractable.

AB - Given a constraint satisfaction problem (CSP) on n variables, x1; x2; : : : ; xn 2 ( ±1), andmconstraints, a global cardinality constraint has the form of Pn i=1 xi = (1 2p)n, where p ∈ ((1); 1 (1)) and pn is an integer. Let AV G be the expected number of constraints satisfied by randomly choosing an assignment to x1; x2; : : : ; xn, complying with the global cardinality constraint. The CSP above average with the global cardinality constraint problem asks whether there is an assignment (complying with the cardinality constraint) that satisfies more than (AV G + t) constraints, where t is an input parameter. In this paper, we present an algorithm that finds a valid assignment satisfying more than (AV G + t) constraints (if there exists one) in time (2O(t2) + nO(d)). Therefore, the CSP above average with the global cardinality constraint problem is fixed-parameter tractable.

UR - http://www.scopus.com/inward/record.url?scp=85016201573&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016201573&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.23

DO - 10.1137/1.9781611974782.23

M3 - Conference contribution

AN - SCOPUS:85016201573

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 358

EP - 377

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery,

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -