Weighted geometric set cover via quasi-uniform sampling
From MaRDI portal
Publication:2875191
DOI10.1145/1806689.1806777zbMath1293.68300OpenAlexW1986685589MaRDI QIDQ2875191
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806777
Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Tighter estimates for \(\epsilon\)-nets for disks ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Unsplittable coverings in the plane ⋮ Hypergraph representation via axis-aligned point-subspace cover ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ On the geometric set multicover problem ⋮ Minimum power partial multi-cover on a line ⋮ Improved results on geometric hitting set problems ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Polychromatic colorings of unions of geometric hypergraphs ⋮ Capacitated covering problems in geometric spaces ⋮ Geometric Packing under Nonuniform Constraints ⋮ On the geometric priority set cover problem ⋮ Octants are cover-decomposable ⋮ Geometric dominating-set and set-cover via local-search ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Constructing planar support for non-piercing regions ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Octants are cover-decomposable into many coverings ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ Fair Scheduling via Iterative Quasi-Uniform Sampling ⋮ Planar Support for Non-piercing Regions and Applications ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Packing and covering with non-piercing regions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for the connected sensor cover problem ⋮ On Geometric Set Cover for Orthants ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Approximability of covering cells with line segments ⋮ When are epsilon-nets small? ⋮ On Capacitated Set Cover Problems ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ A primal-dual algorithm for the minimum power partial cover problem ⋮ On Partial Covering For Geometric Set Systems ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Unnamed Item ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
