Polynomial approximation algorithms with performance guarantees: an introduction-by-example

DOI10.1016/j.ejor.2004.03.021zbMath1062.90053OpenAlexW2036029948MaRDI QIDQ1771343

Vangelis Th. Paschos, Marc Demange

Publication date: 21 April 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.03.021

zbMATH Keywords

Traveling salesmanCombinatorial optimizationComplexity theoryComputing science

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Complexity and performance of numerical algorithms (65Y20)

Related Items (2)

Reductions, completeness and the hardness of approximability ⋮ Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Optimization, approximation, and complexity classes
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Improved approximations for maximum independent set via approximation chains
• Proof verification and the hardness of approximation problems
• On the approximability of the traveling salesman problem (extended abstract)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Greedy Heuristic for the Set-Covering Problem
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• P-Complete Approximation Problems
• Tight bounds for christofides' traveling salesman heuristic
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• The Traveling Salesman Problem with Distances One and Two
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems

This page was built for publication: Polynomial approximation algorithms with performance guarantees: an introduction-by-example