A Probabilistic Approach to Problems Parameterized above or below Tight Bounds

DOI10.1007/978-3-642-11269-0_19zbMath1273.68176OpenAlexW2125649319MaRDI 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

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

Related Items (7)

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

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

This page was built for publication: A Probabilistic Approach to Problems Parameterized above or below Tight Bounds