Elbassioni, Khaled
Finding Small Hitting Sets in Infinite Range Spaces of Bounded VCDimension
Abstract
We consider the problem of finding a small hitting set in an infinite range space F=(Q,R) of bounded VCdimension. We show that, under reasonably general assumptions, the infinitedimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any delta>0, a set of size O(s_F(z^*_F)) that hits (1delta)fraction of R (with respect to a given measure) in time proportional to log(1/delta), where s_F(1/epsilon) is the size of the smallest epsilonnet the range space admits, and z^*_F is the value of the fractional optimal solution. This exponentially improves upon previous results which achieve the same approximation guarantees with running time proportional to poly(1/delta). Our assumptions hold, for instance, in the case when the range space represents the visibility regions of a polygon in the plane, giving thus a deterministic polynomialtime O(log z^*_F)approximation algorithm for guarding (1delta)fraction of the area of any given simple polygon, with running time proportional to polylog(1/delta).
BibTeX  Entry
@InProceedings{elbassioni:LIPIcs:2017:7228,
author = {Khaled Elbassioni},
title = {{Finding Small Hitting Sets in Infinite Range Spaces of Bounded VCDimension}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {40:140:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7228},
URN = {urn:nbn:de:0030drops72289},
doi = {10.4230/LIPIcs.SoCG.2017.40},
annote = {Keywords: VCdimension, approximation algorithms, fractional covering, multiplicative weights update, art gallery problem, polyhedral separators, geometric cove}
}
20.06.2017
Keywords: 

VCdimension, approximation algorithms, fractional covering, multiplicative weights update, art gallery problem, polyhedral separators, geometric cove 
Seminar: 

33rd International Symposium on Computational Geometry (SoCG 2017)

Issue date: 

2017 
Date of publication: 

20.06.2017 