## Abstract

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{script} of geometric objects, compute the minimum-sized subset of P that hits all objects in D{script}. For the case where D{script} is a set of disks in the plane, a PTAS was finally achieved in 2010, with a surprisingly simple algorithm based on local-search. 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. That leaves open the question of whether a better understanding - both combinatorial and algorithmic - of local search and the problem can give a better approximation ratio in a more reasonable time. In this paper, we investigate this question for hitting sets for disks in the plane. We present tight approximation bounds for (3, 2)- local search and give an (8 + ∈)-approximation algorithm with expected running time Õ(n^{2.34}); the previous-best result achieving a similar approximation ratio gave a 10-approximation in time O(n^{15}) - that too just for unit disks. The techniques and ideas generalize to (4, 3) local search. Furthermore, as mentioned earlier, local-search has been used for several other geometric optimization problems; for all these problems our results show that (3, 2) local search gives an 8-approximation and no better1. Similarly (4, 3)-local search gives a 5-approximation for all these problems.

Original language | English (US) |
---|---|

Title of host publication | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 |

Editors | Ernst W. Mayr, Nicolas Ollinger |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 184-196 |

Number of pages | 13 |

ISBN (Electronic) | 9783939897781 |

DOIs | |

State | Published - Feb 1 2015 |

Event | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 - Garching, Germany Duration: Mar 4 2015 → Mar 7 2015 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 30 |

ISSN (Print) | 1868-8969 |

### Other

Other | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 |
---|---|

Country/Territory | Germany |

City | Garching |

Period | 3/4/15 → 3/7/15 |

## Keywords

- Delaunay triangulation
- Disks
- Geometric algorithms
- Hitting sets
- Local search

## ASJC Scopus subject areas

- Software