Domination analysis of combinatorial optimization problems.

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

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

Publication date: 9 September 2003

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

zbMATH Keywords

Combinatorial optimization; Domination analysis; Approximation algorithms

Mathematics Subject Classification ID

90C27: Combinatorial optimization

68W25: Approximation algorithms

Related Items

Domination analysis for minimum multiprocessor scheduling, Greedy-type resistance of combinatorial problems, Dominance guarantees for above-average solutions

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