Solving MAX-r-SAT above a tight lower bound
From MaRDI portal
Publication:644808
DOI10.1007/S00453-010-9428-7zbMATH Open1242.68118OpenAlexW3137355438MaRDI QIDQ644808FDOQ644808
Authors: Noga Alon, G. Gutin, Eun Jung Kim, Stefan Szeider, A. Yeo 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Graph theory
- Parameterizing above or below guaranteed values
- On problems without polynomial kernels
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Betweenness parameterized above tight lower bound
- Title not available (Why is that?)
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Some optimal inapproximability results
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- Title not available (Why is that?)
- The linear arrangement problem parameterized above guaranteed value
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Kernelization: new upper and lower bound techniques
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- Interval Completion Is Fixed Parameter Tractable
- A probabilistic approach to problems parameterized above or below tight bounds
- Improving exact algorithms for MAX-2-SAT
- Fixed-parameter complexity of minimum profile problems
- Algorithms with large domination ratio
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- On the advantage over a random assignment
Cited In (42)
- Long directed detours: reduction to 2-disjoint paths
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Solving #SAT and MAXSAT by Dynamic Programming
- Parameterizations of test cover with bounded test sizes
- Parameterized algorithms for finding square roots
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Title not available (Why is that?)
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Title not available (Why is that?)
- A complete parameterized complexity analysis of bounded planning
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Parameterized traveling salesman problem: beating the average
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- On the parallel parameterized complexity of MaxSAT variants
- Improved parameterized algorithms for above average constraint satisfaction
- Parameterized pre-coloring extension and list coloring problems
- Linear kernels and linear-time algorithms for finding large cuts
- Basic Terminology, Notation and Results
- Faster existential FO model checking on posets
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Domination above \(r\)-independence: does sparseness help?
- Parameterized aspects of strong subgraph closure
- The complexity of degree anonymization by vertex addition
- Alternative parameterizations of \textsc{Metric Dimension}
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Meta-kernelization using well-structured modulators
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Finding detours is fixed-parameter tractable
- Parameterized aspects of strong subgraph closure
- A completeness theory for polynomial (Turing) kernelization
- Turán’s Theorem Through Algorithmic Lens
- Large independent sets in triangle-free planar graphs
- On some FPT problems without polynomial Turing compressions
- Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
- Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
- Simultaneous approximation of constraint satisfaction problems
- Parameterized complexity and kernelizability of max ones and exact ones problems
- Parameterized constraint satisfaction problems: a survey
- Fixed-parameter tractability of satisfying beyond the number of variables
This page was built for publication: Solving MAX-\(r\)-SAT above a tight lower bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q644808)
