Polynomial-time approximation schemes for packing and piercing fat objects

2003/02/01 by Timothy M. Chan, Timothy M Chan · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Dimension (graph theory) #Disjoint sets #Geometry #Mathematical analysis #Mathematics #Packing problems #Point (geometry) #Polynomial #Polynomial-time approximation scheme #Set (abstract data type) #Subdivision #Time complexity

paper · doi:10.1016/s0196-6774(02)00294-8

crossref issued 2003/02/01 · crossref published 2003/02/01 · crossref published-print 2003/02/01 · openalex publication_date 2003/02/01 · crossref created 2003/04/07 · crossref deposited 2019/03/30 · openalex created_date 2025/10/10 · crossref indexed 2026/03/29 · openalex updated_date 2026/07/28

Citations

• Geometric separator theorems and applications
• A tight analysis of the greedy algorithm for set cover
• Applications of a Planar Separator Theorem
• Optimal packing and covering in the plane are NP-complete
• Clique is hard to approximate within n1−ε
• A threshold of ln n for approximating set cover
• Approximation algorithms for NP-complete problems on planar graphs

Cited by

• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Independent set (graph theory) [wikipedia]