Clusters and covers: geometric set cover algorithms

Matthew Richard Gibson

doi:10.17077/etd.frlw4u2t

The set cover problem is a well studied problem in computer science. The problem cannot be approximated to better than an log n-factor in polynomial time unless P = NP and has an O(log n)-factor approximation algorithm. We consider several special cases of the set cover problem in which geometry plays a key role. With geometric structure introduced to the problem, it may be possible to construct approximation algorithms with approximation ratios asymptotically better than log n. The first problem we consider is the decomposing coverings problem. Here, we consider a combinatorial problem: given a collection of points in the plane and a collection of objects in the plane such that each point is contained in at least k objects, partition the objects into as many sets as possible so that each set covers all of the points. We show that if the objects are translates of a convex polygon, then it is possible to partition the translates into Ω(k) covers. The second problem we consider is the planar sensor cover problem. This problem is a generalization of the decomposing coverings problem. We are given a collection of points in the plane and a collection of objects in the plane. Each of the objects can be thought of as a sensor. The sensors have a duration which can be thought of as the battery life of the sensor. The planar sensor cover problem is to schedule a start time to each of the sensors so that the points are covered by a sensor for as long as possible. We give a constant factor approximation for this problem. The key contribution to this result is a constant factor approximation to a one-dimensional version of the problem called the restricted strip cover (RSC) problem. Our result for RSC improves upon the previous best O(log log log n)-approximation, and our result for the planar sensor cover problem improves upon the previous best O(log n)-approximation. The next problem we consider is the metric clustering to minimize the sum of radii problem. Here, we are given an n-point metric (P,d) and an integer k > 0. We are interested in covering the points in P with at most k balls so that the sum of the radii of the balls is minimized. We give a randomized algorithm which solves the problem exactly in nO(log n log Δ) time, where Δ is the ratio of the maximum interpoint distance to the minimum interpoint distance. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and when the metric has constant doubling dimension. The last problem we consider is the minimum dominating set problem for disk graphs. In this problem, we are given a set of disks in the plane, and we want to choose a minimum-cardinality subset of disks such that every disk is either in the set or intersects a disk in the set. For any ε > 0, we show that a simple local search algorithm is a (1+ ε)-approximation for the problem which improves upon the previous best O(log n)-approximation algorithm.

Clusters and covers: geometric set cover algorithms

Files and links (1)

Abstract

Details

Metrics