Approximation Algorithms for Geometric Clustering and Touring Problems

Abstract

Clustering and touring are two fundamental topics in optimization that have been studied extensively and have ``launched a thousand ships''. In this thesis, we study variants of these problems for Euclidean instances, in which clusters often correspond to sensors that are required to cover, measure or localize targets and tours need to visit locations for the purpose of item delivery or data collection. In the first part of the thesis, we focus on the task of sensor placement for environments in which localization is a necessity and in which its quality depends on the relative angle between the target and the pair of sensors observing it. We formulate a new coverage constraint that bounds this angle and consider the problem of placing a small number of sensors that satisfy it in addition to classical ones such as proximity and line-of-sight visibility. We present a general framework that chooses a small number of sensors and approximates the coverage constraint to arbitrary precision. In the second part of the thesis, we consider the task of collecting data from a set of sensors by getting close to them. This corresponds to a well-known generalization of the Traveling Salesman Problem (TSP) called TSP with Neighborhoods, in which we want to compute a shortest tour that visits at least one point from each unit disk centered at a sensor. One approach is based on an observation that relates the optimal solution with the optimal TSP on the sensors. We show that the associated bound can be improved unless we are in certain exceptional circumstances for which we can get better algorithms. Finally, we discuss Maximum Scatter TSP, which asks for a tour that maximizes the length of the shortest edge. While the Euclidean version admits an efficient approximation scheme and the problem is known to be NP-hard in three dimensions or higher, the question of getting a polynomial time algorithm for two dimensions remains open. To this end, we develop a general technique for the case of points concentrated around the boundary of a circle that we believe can be extended to more general cases.