Polynomial approximation algorithms with performance guarantees: an introduction-by-example
type: Item
instance of: scholarly article
title: Polynomial approximation algorithms with performance guarantees: an introduction-by-example
zbMATH Open document ID: 1062.90053
author: Vangelis Th. Paschos
author: Marc Demange
published in: European Journal of Operational Research
publication date: 2005-04-21T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 2159746
zbMATH Keywords: Combinatorial optimization
zbMATH Keywords: Computing science
zbMATH Keywords: Complexity theory
zbMATH Keywords: Traveling salesman
MaRDI profile type: Publication
full work available at URL: j.ejor.2004.03.021
OpenAlex ID: W2036029948
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: Proof verification and the hardness of approximation problems
cites work: Q4258216
cites work: Q3221758
cites work: Q3941433
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Tight bounds for christofides' traveling salesman heuristic
cites work: Improved approximations for maximum independent set via approximation chains
cites work: Q4535019
cites work: Q4198056
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Q3002852
cites work: Approximation algorithms for combinatorial problems
cites work: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
cites work: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
cites work: Q4130999
cites work: On the ratio of optimal integral and fractional covers
cites work: Ramsey numbers and an approximation algorithm for the vertex cover problem
cites work: On the approximability of the traveling salesman problem (extended abstract)
cites work: Optimization, approximation, and complexity classes
cites work: The Traveling Salesman Problem with Distances One and Two
cites work: Q4527015
cites work: P-Complete Approximation Problems
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
DOI: 10.1016/J.EJOR.2004.03.021
description: scientific article; zbMATH DE number 2159746