Norbert Bus, PhD

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, the 30-year quest for a PTAS, starting from the seminal work of Hochbaum, was finally achieved in 2010. Surprisingly, the algorithm to achieve the PTAS is simple: local-search. In particular, the algorithm starts with any hitting set, and iteratively tries to decrease its size by trying to replace some k points by k-1 points; call such an algorithm a (k,k-1)-local search algorithm. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. In particular, the current best work shows that if k>=30, then local-search is able to give a constant factor (as a function of k) approximation ratio. Unfortunately this then implies that the running time for local-search to provably work at all is Ω(n^30) using the current framework. As currently local search is the only known method that gives approximation factors that could be useful in practice, it becomes important to explore the limits in both efficiency and quality of local search. Simple examples show that (1,0) and (2,1) local search cannot give constant factor approximations. In this paper, we show that, surprisingly, just (3,2) local search is able to give a constant-factor approximation; in fact we are able to get the precise quality limit of (3,2)-local search: factor 8 approximation. This simplest working instance of local search already gives an approximation factor that is better than all known other methods! In fact, our improvement applies to all algorithms that use local-search for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others. Finding efficient (3,2)-local search algorithms then becomes the key bottleneck in efficient and good-quality algorithms. In this paper we present such improved algorithms.

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, the 30-year quest for a PTAS, starting from the seminal work of Hochbaum-Mass, was finally achieved by Mustafa-Ray. Surprisingly, the algorithm to achieve the PTAS is simple: local-search. Since then, several open problems on PTAS have been resolving using similar analysis by local-search. Unfortunately these algorithms have a severe limitation: local search gives a PTAS, but with hopeless running times; e.g., a 3-approximation takes more than n⁶⁶ time for the geometric hitting set problem for disks in the plane. That leaves the question of whether a better analysis - both combinatorial and algorithmic - of local search can give a better approximation ratio in a more reasonable time. We show that this can indeed be done via a better understanding of the underlying geometric and combinatorial structure. We present tight approximation bounds for (3,2)-local search and give an (8 + &epsilon)-approximation algorithm with running time O(n^2.34). Local search has turned out to be a powerful tool for certain geometric optimization problems and has been used to give a PTAS for a several problems: independent set of pseudodisks, dominating sets in disk intersection graphs, terrain guarding problem and several other problems. For all these problems our results show that (3,2) local search gives an 8-approximation and no better.