Approximation Algorithms for Geometric Packing and Covering Problems
Author
Roy, Aniket Basu
Metadata
Show full item recordAbstract
We study a host of geometric optimization problems that are NPhard 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 nonpiercing regions in the plane. We call a set of simple and connected regions to be nonpiercing if for any pair of intersecting regions, A and B both A\B and B\A are connected regions. A set of disks, squares, halfplanes are examples of nonpiercing 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 sublinear 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 nonpiercing whereas for the latter problem the objects can be even more general and only have subquadratic union complexity with the capacities at most some constant for both the cases. The nontriviality here is to show that the intersection graph of arrangements with shallow depth, which is not planar, has balanced sublinear 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 BrannamanGoodrich technique for packing problems.
Runaway Rectangle Escape problem is closely related to the above packing problems and is motivated from routing in printed circuit boards. Here we are given a set of axisparallel rectangles inside a rectangular boundary R and a maximum allowed depth d. The objective is to extend the maximum number of input rectangles to one of the four sides of R such that the maximum depth of a point is at most d after extension. We show that local search gives a (2 + )approximation for d = O(1). When the input rectangles are all disjoint then we devise a simple 4(1 + 1=(d 1))approximation algorithm. We also propose a randomized (1 + )approximation algorithm based on randomized rounding making some density assumptions. Lastly, we show the problem to be NPhard even when the rectangles are unit squares aligned in a grid.
We study the MultiCover problem which is a generalization of the Set Cover problem. We give a PTAS for nonpiercing regions when the depth of every point is at most constant. We also study different variants of the covering problem like the Unique Coverage, and Prize Collecting Set Cover problem. For Unique Cover we show that local search yields a PTAS for nonpiercing regions for bounded depth and degree. For Prize Collecting Set Cover a PTAS works for nonpiercing regions if the weight of every region is within a range [1; a], where a is some constant.
Lastly, we consider variants of the Art Gallery problems called the Minimum (Horizontal) Sliding Cameras problem, M(H)SC. We are given an orthogonal polygon and we need to deploy mobile guards who can walk along an orthogonal (horizontal) line segment and can guard a point inside the polygon if the perpendicular drawn from the point onto the line segment lies inside the polygon. Our local search algorithm yields a PTAS for the MHSC problem and also the MSC problem when the polygon has no holes. In order to do so we prove an appropriate graph on orthogonal line segments to be planar by proposing a graph drawing scheme.
Collections
Related items
Showing items related by title, author, creator and subject.

Some Theoretical Contributions To The Mutual Exclusion Problem ï»¿
Alagarsamy, K (20121204) 
Batch Processsor Scheduling  A Class Of Problems In Steel Casting Foundries ï»¿
Ramasubramaniam, M (20100915)Modern manufacturing systems need new types of scheduling methods. While traditional scheduling methods are primarily concerned with sequencing of jobs, modern manufacturing environments provide the additional possibility ... 
Schemes for Smooth Discretization And Inverse Problems  Case Study on Recovery of Tsunami Source Parameters ï»¿
Devaraj, G (20171017)This thesis deals with smooth discretization schemes and inverse problems, the former used in efficient yet accurate numerical solutions to forward models required in turn to solve inverse problems. The aims of the thesis ...