Note on Max Lin-2 above average

DOI10.1016/j.ipl.2010.04.010zbMath1229.68044arXiv0911.5384OpenAlexW2161307522MaRDI QIDQ656604

Juan-Miguel Gracia

Publication date: 18 January 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.5384

zbMATH Keywords

fixed-parameter tractabilityMax LinMax Sat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the complexity of and solutions to the minimum stopping and trapping set problems ⋮ 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 ⋮ Note on maximal bisection above tight lower bound ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ 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 ⋮ Betweenness parameterized above tight lower bound ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter complexity of minimum profile problems
• Parameterizing above or below guaranteed values
• The linear arrangement problem parameterized above guaranteed value
• Parametrized complexity theory.
• Interval Completion Is Fixed Parameter Tractable
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On the advantage over a random assignment