Solving MAX-\(r\)-SAT above a tight lower bound
From MaRDI portal
Publication:644808
DOI10.1007/s00453-010-9428-7zbMath1242.68118MaRDI QIDQ644808
Gregory Gutin, Anders Yeo, Noga Alon, Stefan Szeider, Eun Jung Kim
Publication date: 7 November 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9428-7
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improving exact algorithms for MAX-2-SAT
- Fixed-parameter complexity of minimum profile problems
- Parameterizing above or below guaranteed values
- On problems without polynomial kernels
- Some simplified NP-complete graph problems
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Betweenness parameterized above tight lower bound
- The linear arrangement problem parameterized above guaranteed value
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Interval Completion Is Fixed Parameter Tractable
- Kernelization: New Upper and Lower Bound Techniques
- A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Algorithms with large domination ratio
- Some optimal inapproximability results
- On the advantage over a random assignment
