A Probabilistic Approach to Problems Parameterized above or below Tight Bounds

DOI10.1007/978-3-642-11269-0_19zbMath1273.68176MaRDI QIDQ3656865

Stefan Szeider, Gregory Gutin, Anders Yeo, Eun Jung Kim

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_19

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

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, Lower bounds on kernelization, Solving MAX-\(r\)-SAT above a tight lower bound, Note on Max Lin-2 above average, Note on maximal bisection above tight lower bound, Betweenness parameterized above tight lower bound, Improved Parameterized Algorithms for above Average Constraint Satisfaction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter complexity of minimum profile problems
• Parameterizing above or below guaranteed values
• Solving linear equations over GF(2): Block Lanczos algorithm
• Voting paradoxes and digraphs realizations
• Betweenness parameterized above tight lower bound
• The linear arrangement problem parameterized above guaranteed value
• Parametrized complexity theory.
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Algorithms with large domination ratio
• Digraphs
• On the advantage over a random assignment