Parameterized complexity of MaxSat above average
From MaRDI portal
Publication:392026
DOI10.1016/j.tcs.2013.01.005zbMath1358.68126arXiv1108.4501OpenAlexW1974828352MaRDI QIDQ392026
Publication date: 13 January 2014
Published in: Theoretical Computer Science, LATIN 2012: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.4501
Related Items (8)
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\) ⋮ Parameterized complexity of MaxSat above average ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Unnamed Item ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Incremental problems in the parameterized complexity setting
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of MaxSat above average
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- A probabilistic approach to problems parameterized above or below tight bounds
- Solving MAX-\(r\)-SAT above a tight lower bound
- A simplified NP-complete satisfiability problem
- Which problems have strongly exponential complexity?
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Parametrized complexity theory.
- On Multiway Cut Parameterized above Lower Bounds
- Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
- A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
- Paths, Flowers and Vertex Cover
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- Parameterizing MAX SNP Problems Above Guaranteed Values
- Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
- On the power of unique 2-prover 1-round games
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Faster Parameterized Algorithms Using Linear Programming
- On the complexity of \(k\)-SAT
This page was built for publication: Parameterized complexity of MaxSat above average
