Algorithms with large domination ratio
From MaRDI portal
Publication:4819698
DOI10.1016/j.jalgor.2003.09.003zbMath1068.68175OpenAlexW2092509105MaRDI QIDQ4819698
Michael Krivelevich, Noga Alon, Gregory Gutin
Publication date: 4 October 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jalgor.2003.09.003
Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (24)
Fast Heuristics and Approximation Algorithms ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\) ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ Unnamed Item ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Hamilton decompositions of regular expanders: applications ⋮ Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Dominance guarantees for above-average solutions ⋮ Quadratic forms on graphs ⋮ Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width ⋮ Tournament quasirandomness from local counting ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Anticoncentration for subgraph statistics ⋮ On the advantage over a random assignment ⋮ Edge-statistics on large graphs ⋮ A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
This page was built for publication: Algorithms with large domination ratio
