Approximating Maximum Independent Set of Polygons – University of Copenhagen

Approximating Maximum Independent Set of Polygons

Talk by Anna Adamaszek, Max-Planck Institute für Informatik

Abstract

The Maximum Weight Independent Set of Polygons (MWISP) problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the two-dimensional plane, the goal is to find a set of pairwise non-overlapping polygons with maximum total weight. Despite a lot of research, the problem is not well-understood yet. The best known hardness result is strong NP-hardness, while the best known polynomial time algorithm achieves an approximation ratio of n^{\epsilon}, even for the special case when all input objects are line segments (or rectangles). We present a (1 + \epsilon)-approximation algorithm, assuming that each polygon in the input has at most a polylogarithmic number of vertices. Our algorithm has quasi-polynomial running time, i.e., it runs in time 2^{poly(log n, 1/\epsilon)}.