The maximum exposure problem

DOI10.1016/J.COMGEO.2022.101861MaRDI QIDQ2123293zbMATH OpenOpenAlexFDO

Authors Neeraj Kumar, Stavros Sintos, Subhash Suri

Publication date 8 April 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.03455, https://drops.dagstuhl.de/opus/volltexte/2019/11234/

zbMATH Keywords

network resiliencePTASdensest k-subgraphgeometric constraint removalmax-exposure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Given a set of points $P$ and axis-aligned rectangles $mathcalR$ in the plane, a point $pinP$ is called emph{exposed} if it lies outside all rectangles in $mathcalR$. In the emph{max-exposure problem}, given an integer parameter $k$, we want to delete $k$ rectangles from $mathcalR$ 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 $mathcalR$ are translates of two fixed rectangles. However, if $mathcalR$ only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, 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.

Recommendations

• Covering points by disjoint boxes with outliers
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Maximum independent set of rectangles
• The class cover problem with boxes
• Covering many points with a small-area box

Cites work

• A threshold of ln n for approximating set cover
• Almost optimal set covers in finite VC-dimension
• Applications of random sampling in computational geometry. II
• Approximation algorithms for union and intersection covering problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Greedily Finding a Dense Subgraph
• Improved approximation bounds for the minimum constraint removal problem
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• On the complexity of barrier resilience for fat regions and bounded ply
• On the set multicover problem in geometric settings
• Optimal packing and covering in the plane are NP-complete
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• The Maximum Exposure Problem.
• The dense \(k\)-subgraph problem
• The densest \(k\)-subhypergraph problem

Cited in

(1)

• On the parameterized complexity of the Maximum Exposure Problem

This page was built for publication: The maximum exposure problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2123293)