Improved Parameterized Algorithms for above Average Constraint Satisfaction

DOI10.1007/978-3-642-28050-4_10zbMath1352.68115arXiv1008.0213OpenAlexW2108633592MaRDI QIDQ2891342

No author found.

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

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

Related Items

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ 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\) ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Unnamed Item ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Acyclic Digraphs ⋮ On subexponential and FPT-time inapproximability

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on exact algorithms for vertex ordering problems on graphs
• Parameterizing above or below guaranteed values
• Betweenness parameterized above tight lower bound
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Approximating Bounded Occurrence Ordering CSPs
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• On the power of unique 2-prover 1-round games
• Confronting hardness using a hybrid approach
• All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
• Kernelization: New Upper and Lower Bound Techniques
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Some optimal inapproximability results