Approximation schemes for geometric NP-hard problems: A survey

DOI10.1007/3-540-45294-X_2MaRDI QIDQ4474203zbMATH OpenFDO

Authors Sanjeev Arora

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2245/22450016.htm

Mathematics Subject Classification ID

Logic programming (68N17) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Review text

For the entire collection see [Zbl 0977.00041].

Recommendations

• Approximation schemes for NP-hard geometric optimization problems: a survey
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Geometric approximation algorithms
• Polynomial-time approximation schemes for geometric graphs
• On the approximation hardness of geodetic set and its variants
• scientific article; zbMATH DE number 7378687
• The computational complexity and approximability of a series of geometric covering problems
• Approximation algorithms for geometrical distance problems that are not solvable exactly
• Hardness and approximation for the geodetic set problem in some graph classes
• On a class of O(n^2) problems in computational geometry

Cited in

(1)

• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

This page was built for publication: Approximation schemes for geometric NP-hard problems: A survey

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