文章基本信息

标题：The Maximum Exposure Problem
本地全文：下载
作者：Neeraj Kumar ; Stavros Sintos ; Subhash Suri 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-20
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：max-exposure; PTAS; densest k-subgraphs; geometric constraint removal; Network resilience