Solving MAX-\(r\)-SAT above a tight lower bound
From MaRDI portal
Publication:644808
DOI10.1007/s00453-010-9428-7zbMath1242.68118OpenAlexW3137355438MaRDI QIDQ644808
Anders Yeo, Gregory Gutin, Eun Jung Kim, Noga Alon, Stefan Szeider
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ 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\) ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Parameterized aspects of strong subgraph closure ⋮ Meta-kernelization using well-structured modulators ⋮ Parameterized complexity of MaxSat above average ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Unnamed Item ⋮ The complexity of degree anonymization by vertex addition ⋮ Unnamed Item ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ Parameterized Traveling Salesman Problem: Beating the Average ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ Unnamed Item ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Faster Existential FO Model Checking on Posets ⋮ Unnamed Item ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ On some FPT problems without polynomial Turing compressions ⋮ Basic Terminology, Notation and Results ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ A complete parameterized complexity analysis of bounded planning ⋮ Parameterizations of test cover with bounded test sizes ⋮ Parameterized algorithms for finding square roots
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
