PhD Defense: Approximation Algorithms for Geometric Clustering and Touring Problems

Talk
Ioana Bercea
Time: 
07.25.2018 09:30 to 11:30
Location: 
AVW 3450

Clustering and touring are two fundamental topics in optimization that have been studied extensively and consequently, attacking different problems in these frameworks has spawned a multitude of techniques. 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. We aim to prove new structural results about such instances and use them to develop algorithms with provable performance guarantees. In the first part of the thesis, we focus on the task of sensor placement for environments in which localization is a necessity, such as sensor arrays tracking a target. The quality of localization often 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 leads to low uncertainty of localization. We then consider the problem of placing a small number of sensors that satisfy this constraint in addition to classical ones such as proximity and line-of-sight visibility. The inherent dependency between sensors makes this problem challenging, since generic clustering techniques do not account for it. We present a general framework that chooses a small number of sensors and approximates the coverage constraint to arbitrary precision in most cases.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 (TSPN), in which we want to compute a shortest tour that visits at least one point from each unit disk centered at a sensor. While an approximation scheme is known for the case of disjoint disks, obtaining practical and good constant factor approximations remains of high interest. The best known approach, by Dumitrescu and Mitchell (2001), is based on an observation that relates the TSPN solution with the optimal TSP on the sensors. In 2011, Hame, Hyytia and Hakula conjectured that the associated bound can be improved and a better factor possible. In our thesis, we show that this bound can indeed be improved unless we are in certain exceptional circumstances for which we can get better algorithms. We achieve this through a structural understanding of the optimal solution and specifically, by developing a novel lower bounding technique for TSPN. Finally, we discuss another version of TSP, called Maximum Scatter TSP, which asks for a tour that maximizes the length of the shortest edge. This is inspired by applications that require consecutive points on the tour to be well separated, such as in manufacturing and medical imaging tasks. 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.
Examining Committee:

Chair: Dr. Samir Khuller Dean's rep: Dr. Mark Shayman Members: Dr. Yiannis Aloimonos Dr. William Gasarch Dr. David Mount