Improved Parameterized Algorithms for above Average Constraint Satisfaction
From MaRDI portal
Publication:2891342
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
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
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