Parameterized complexity of MaxSat above average

DOI10.1016/j.tcs.2013.01.005zbMath1358.68126arXiv1108.4501OpenAlexW1974828352MaRDI QIDQ392026

Mohammad Hasan, H. S. Yoon

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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