The Maximum Exposure Problem.

DOI10.4230/LIPICS.APPROX-RANDOM.2019.19MaRDI QIDQ5875471zbMATH OpenOpenAlexFDO

Authors Neeraj Kumar, Stavros Sintos, Subhash Suri

Publication date 3 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11234/pdf/LIPIcs-APPROX-RANDOM-2019-19.pdf/

zbMATH Keywords

network resiliencePTASgeometric constraint removalmax-exposuredensest \(k\)-subgraphs

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

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 dense \(k\)-subgraph problem
• The densest \(k\)-subhypergraph problem

Cited in

(1)

• 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 Q5875471)