On Geometric Set Cover for Orthants
From MaRDI portal
Publication:5075763
DOI10.4230/LIPIcs.ESA.2019.26OpenAlexW2975342837MaRDI QIDQ5075763
Michał Pilipczuk, Sándor Kisfaludi-Bak, Karl Bringmann, Erik Jan van Leeuwen
Publication date: 11 May 2022
Full work available at URL: https://doi.org/10.4230/lipics.esa.2019.26
Related Items
Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs, Surprising Applications of Treewidth Bounds for Planar Graphs, On the geometric priority set cover problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- A note on the \(\epsilon\)-indicator subset selection
- Improved results on geometric hitting set problems
- Improved approximation algorithms for geometric set cover
- Approximately dominating representatives
- Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
- Finding small simple cycle separators for 2-connected planar graphs
- Optimal packing and covering in the plane are NP-complete
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Which problems have strongly exponential complexity?
- The complexity of dominating set in geometric intersection graphs
- Almost optimal set covers in finite VC-dimension
- Efficiently computing succinct trade-off curves
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Weighted geometric set cover via quasi-uniform sampling
- Approximating Multiobjective Knapsack Problems
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- PTAS for Weighted Set Cover on Unit Squares
- A Greedy Heuristic for the Set-Covering Problem
- Packing and Covering with Non-Piercing Regions
- The limited blessing of low dimensionality
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- Geometric Set Cover and Hitting Sets for Polytopes in R
- Approximation Schemes for Covering and Packing
- Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Analytical approach to parallel repetition
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Orthogonal range searching on the RAM, revisited
- Tight lower bounds for the size of epsilon-nets
- Parameterized Algorithms
- The NP-completeness column: An ongoing guide
- Random knapsack in expected polynomial time
