Approximation Schemes for Independent Set and Sparse Subsets of Polygons
Approximation Schemes for Independent Set and Sparse Subsets of Polygons
We present a (1+ε)-approximation algorithm with quasi-polynomial running time for computing a maximum weight independent set of polygons from a given set of polygons in the plane. Contrasting this, the best-known polynomial time algorithm for the problem has an approximation ratio of n ε . Surprisingly, we can extend the …