Weighted geometric set cover via quasi-uniform sampling

DOI10.1145/1806689.1806777zbMATH Open1293.68300OpenAlexW1986685589MaRDI QIDQ2875191FDOQ2875191

Authors: Kasturi Varadarajan 

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

Recommendations

• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling
• Weighted geometric set multi-cover via quasi-uniform sampling
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Weighted geometric set cover problems revisited

zbMATH Keywords

approximationepsilon netsset cover

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (47)

• Weighted geometric set multi-cover via quasi-uniform sampling
• Algorithms for covering multiple submodular constraints and applications
• On partial covering for geometric set systems
• Tighter estimates for \(\epsilon\)-nets for disks
• Geometric Packing under Nonuniform Constraints
• Improved results on geometric hitting set problems
• Title not available (Why is that?)
• Polychromatic colorings of unions of geometric hypergraphs
• Packing and covering with non-piercing regions
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Title not available (Why is that?)
• Near-linear time approximation schemes for geometric maximum coverage
• On the geometric priority set cover problem
• Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
• PTAS for minimum cost multicovering with disks
• Weighted geometric set cover with rectangles of bounded integer side lengths
• Approximation algorithms for maximum independent set of pseudo-disks
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• A PTAS for the horizontal rectangle stabbing problem
• Octants are cover-decomposable
• Hypergraph representation via axis-aligned point-subspace cover
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Weighted geometric set multi-cover via quasi-uniform sampling
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• A PTAS for the horizontal rectangle stabbing problem
• On the geometric set multicover problem
• A PTAS for the Weighted Unit Disk Cover Problem
• Constructing planar support for non-piercing regions
• Fair scheduling via iterative quasi-uniform sampling
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Title not available (Why is that?)
• On capacitated set cover problems
• On Geometric Set Cover for Orthants
• Geometric dominating-set and set-cover via local-search
• Capacitated covering problems in geometric spaces
• Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
• Minimum power partial multi-cover on a line
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Planar Support for Non-piercing Regions and Applications
• Capacitated covering problems in geometric spaces
• When are epsilon-nets small?
• A primal-dual algorithm for the minimum power partial cover problem
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
• Octants are cover-decomposable into many coverings
• Geometric stabbing via threshold rounding and factor revealing LPs
• Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems

This page was built for publication: Weighted geometric set cover via quasi-uniform sampling

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