Note on Max Lin-2 above average

DOI10.1016/j.ipl.2010.04.010zbMath1229.68044arXiv0911.5384MaRDI 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 tractability; Max Lin; Max Sat

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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, Note on maximal bisection above tight lower bound, Betweenness parameterized above tight lower bound, On the complexity of and solutions to the minimum stopping and trapping set problems, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, 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