2026-07-22T13:39:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11234 2024-03-06T10:47:45Z ddc:004 open_access

The Maximum Exposure Problem Kumar, Neeraj Sintos, Stavros Suri, Subhash max-exposure PTAS densest k-subgraphs geometric constraint removal Network resilience Given a set of points P and axis-aligned rectangles R in the plane, a point p in P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k^2) rectangles, we can expose at least Omega(1/k) of the optimal number of points. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Neeraj Kumar and Stavros Sintos and Subhash Suri 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.19 urn:nbn:de:0030-drops-112344 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.19 eng https://creativecommons.org/licenses/by/3.0/legalcode