#### Document Type

Dissertation

#### Date of Degree

Spring 2010

#### Degree Name

PhD (Doctor of Philosophy)

#### Degree In

Computer Science

#### First Advisor

Kasturi Varadarajan

#### Abstract

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 *n*^{O(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.

#### Keywords

approximation algorithms, computational geometry, decomposing coverings, sensor cover, set cover

#### Pages

x, 122 pages

#### Bibliography

Includes bibliographical references (pages 117-122).

#### Copyright

Copyright 2010 Matthew Richard Gibson