Algorithms with large domination ratio

DOI10.1016/J.JALGOR.2003.09.003MaRDI QIDQ4819698zbMATH OpenOpenAlexFDO

Authors Noga Alon, G. Gutin, Michael Krivelevich

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

zbMATH Keywords

optimization problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Recommendations

• Domination analysis for minimum multiprocessor scheduling
• Approximating theDomatic Number
• scientific article; zbMATH DE number 1342117
• Approximating the domatic number
• Domination analysis of combinatorial optimization problems.

Cited in

(28)

• Algorithmic aspects of majority domination
• A probabilistic approach to problems parameterized above or below tight bounds
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Anticoncentration for subgraph statistics
• Hamilton decompositions of regular expanders: applications
• Solving MAX-\(r\)-SAT above a tight lower bound
• A probabilistic approach to problems parameterized above or below tight bounds
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
• Quadratic forms on graphs
• Kernelization -- preprocessing with a guarantee
• Fast heuristics and approximation algorithms
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Tournament quasirandomness from local counting
• A domination algorithm for \(\{0,1\}\)-instances of the travelling salesman problem
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Edge-statistics on large graphs
• Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System
• The inertia bound is far from tight
• Combinatorial dominance guarantees for problems with infeasible solutions
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• On the advantage over a random assignment
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• The bilinear assignment problem: complexity and polynomially solvable special cases
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• Domination analysis for minimum multiprocessor scheduling
• Dominance guarantees for above-average solutions
• Domination analysis of combinatorial optimization problems.
• Parameterized constraint satisfaction problems: a survey

This page was built for publication: Algorithms with large domination ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4819698)