Domination analysis of combinatorial optimization problems.

DOI10.1016/S0166-218X(03)00359-7zbMath1052.90062OpenAlexW2084173720MaRDI QIDQ1406045

Anders Yeo, Gregory Gutin, A. D. Vaĭnshteĭn

Publication date: 9 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00359-7

zbMATH Keywords

Combinatorial optimizationDomination analysisApproximation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (7)

Domination analysis for minimum multiprocessor scheduling ⋮ Greedy-type resistance of combinatorial problems ⋮ 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 ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Dominance guarantees for above-average solutions ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• Transformations of generalized ATSP into ATSP.
• Domination analysis of greedy heuristics for the frequency assignment problem.
• TSP heuristics: domination analysis and complexity
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Domination analysis of some heuristics for the traveling salesman problem
• z-Approximations
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• The approximation of maximum subgraph problems

This page was built for publication: Domination analysis of combinatorial optimization problems.