Improved parameterized algorithms for above average constraint satisfaction

DOI10.1007/978-3-642-28050-4_10MaRDI QIDQ2891342zbMATH OpenOpenAlexFDO

Authors Eun Jung Kim, Ryan Williams

Publication date 15 June 2012

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.0213

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Abstract: For many constraint satisfaction problems, the algorithm which chooses a random assignment achieves the best possible approximation ratio. For instance, a simple random assignment for {sc Max-E3-Sat} allows 7/8-approximation and for every $eps>0$ there is no polynomial-time ($7/8+eps$)-approximation unless P=NP. Another example is the {sc Permutation CSP} of bounded arity. Given the expected fraction $ho$ of the constraints satisfied by a random assignment (i.e. permutation), there is no $(ho+eps)$-approximation algorithm for every $eps>0$, assuming the Unique Games Conjecture (UGC). In this work, we consider the following parameterization of constraint satisfaction problems. Given a set of $m$ constraints of constant arity, can we satisfy at least $hom+k$ constraint, where $ho$ is the expected fraction of constraints satisfied by a random assignment? {sc Constraint Satisfaction Problems above Average} have been posed in different forms in the literature cite{Niedermeier2006,MahajanRamanSikdar09}. We present a faster parameterized algorithm for deciding whether $m/2+k/2$ equations can be simultaneously satisfied over ${mathbbF}_2$. As a consequence, we obtain $O(k)$-variable bikernels for {sc boolean CSPs} of arity $c$ for every fixed $c$, and for {sc permutation CSPs} of arity 3. This implies linear bikernels for many problems under the "above average" parameterization, such as {sc Max-$c$-Sat}, {sc Set-Splitting}, {sc Betweenness} and {sc Max Acyclic Subgraph}. As a result, all the parameterized problems we consider in this paper admit $2^{O(k)}$-time algorithms. We also obtain non-trivial hybrid algorithms for every Max $c$-CSP: for every instance $I$, we can either approximate $I$ beyond the random assignment threshold in polynomial time, or we can find an optimal solution to $I$ in subexponential time.

Recommendations

• Parameterized constraint satisfaction problems: a survey
• Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Solving MAX-\(r\)-SAT above a tight lower bound

Cites work

• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• scientific article; zbMATH DE number 6297727 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A note on exact algorithms for vertex ordering problems on graphs
• A probabilistic approach to problems parameterized above or below tight bounds
• All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
• Approximating Bounded Occurrence Ordering CSPs
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Betweenness parameterized above tight lower bound
• Confronting hardness using a hybrid approach
• Kernelization: new upper and lower bound techniques
• On the power of unique 2-prover 1-round games
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Some optimal inapproximability results
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average

Cited in

(11)

• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Acyclic digraphs
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
• Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints
• Parameterized constraint satisfaction problems: a survey

Describes a project that uses

Uses Software

• Outward rotations

This page was built for publication: Improved parameterized algorithms for above average constraint satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891342)