TY - GEN

T1 - Finding small hitting sets in infinite range spaces of bounded VC-Dimension

AU - Elbassioni, Khaled

N1 - Publisher Copyright:
© Khaled Elbassioni.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - We consider the problem of finding a small hitting set in an infinite range space F = (Q, R) of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite-dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any δ > 0, a set of size O(sF(z∗F) that hits (1 - δ)-fraction of R (with respect to a given measure) in time proportional to log(1δ), where sF(1/ϵ) is the size of the smallest ϵ-net 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/δ). Our assumptions hold, for instance, in the case when the range space represents the visibility regions of a polygon in ℝ2 giving thus a deterministic polynomial-time O (log z∗F) -approximation algorithm for guarding (1 - δ)-fraction of the area of any given simple polygon, with running time proportional to polylog(1/δ).

AB - We consider the problem of finding a small hitting set in an infinite range space F = (Q, R) of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite-dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any δ > 0, a set of size O(sF(z∗F) that hits (1 - δ)-fraction of R (with respect to a given measure) in time proportional to log(1δ), where sF(1/ϵ) is the size of the smallest ϵ-net 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/δ). Our assumptions hold, for instance, in the case when the range space represents the visibility regions of a polygon in ℝ2 giving thus a deterministic polynomial-time O (log z∗F) -approximation algorithm for guarding (1 - δ)-fraction of the area of any given simple polygon, with running time proportional to polylog(1/δ).

KW - Approximation algorithms

KW - Art gallery problem

KW - Fractional covering

KW - Geometric covering

KW - Multiplicative weights update

KW - Polyhedral separators

KW - Vc-dimension

UR - http://www.scopus.com/inward/record.url?scp=85029957738&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2017.40

DO - 10.4230/LIPIcs.SoCG.2017.40

M3 - Conference contribution

AN - SCOPUS:85029957738

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 401

EP - 4015

BT - 33rd International Symposium on Computational Geometry, SoCG 2017

A2 - Katz, Matthew J.

A2 - Aronov, Boris

T2 - 33rd International Symposium on Computational Geometry, SoCG 2017

Y2 - 4 July 2017 through 7 July 2017

ER -