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, 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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item