Treffer: Approximation Algorithms for Geometric Packing and Covering Problems

We study a host of geometric optimization problems that are NP-hard and design polynomial time approximation algorithms for them. More precisely, we are given a family of geometric objects and a point set, mostly in the plane, and study different variants and generalizations of Packing and Covering problems. Our objects of study are mostly family of non-piercing regions in the plane. We call a set of simple and connected regions to be non-piercing if for any pair of intersecting regions, A and B both A\B and B\A are connected regions. A set of disks, squares, half-planes are examples of non-piercing regions, whereas, a set of lines, rectangles are examples of piercing objects. For most of the problems we have studied, a simple local search algorithm is enough to yield a PTAS whose analysis of approximation requires a suitable bipartite graph on the local search solution and the optimal solution to have a balanced sub-linear separator. We study a generalization of the standard packing problem, called the Capacitated Region Packing problem and its slight variant, the Shallow Packing problem. We devise a PTAS for both these problems with restrictions on the capacities. For the former problem, the objects are non-piercing whereas for the latter problem the objects can be even more general and only have sub-quadratic union complexity with the capacities at most some constant for both the cases. The non-triviality here is to show that the intersection graph of arrangements with shallow depth, which is not planar, has balanced sub-linear separators. Our results complement the Maximum Independent Set of Rectangles problem as rectangles are both piercing and have quadratic union complexity. We also study the Shallow Point Packing problem and are able to show that local search works here as well for unit capacity and devise a constant factor approximation algorithm using an adaptation Brannaman-Goodrich technique for packing problems. Runaway Rectangle Escape problem is closely related to the above packing problems and is ...