Note on Max Lin-2 above average
From MaRDI portal
Publication:656604
DOI10.1016/j.ipl.2010.04.010zbMath1229.68044arXiv0911.5384MaRDI QIDQ656604
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
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