Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
From MaRDI portal
Publication:5743501
zbMATH Open1421.68198MaRDI QIDQ5743501FDOQ5743501
Authors: Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe 
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095241
Recommendations
- Weighted geometric set multi-cover via quasi-uniform sampling
- Weighted geometric set multi-cover via quasi-uniform sampling
- Weighted geometric set cover via quasi-uniform sampling
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Exact and approximation algorithms for geometric and capacitated set cover problems
Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Approximation algorithms for NP-hard problems.
- Title not available (Why is that?)
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Voronoi diagrams in higher dimensions under certain polyhedral distance functions
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Almost optimal set covers in finite VC-dimension
- Weighted geometric set cover via quasi-uniform sampling
- Epsilon nets and union complexity
- Computational geometry. Algorithms and applications.
- Flows and generalized coloring theorems in graphs
- Title not available (Why is that?)
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- On a set of almost deterministic k-independent random variables
- On column-restricted and priority covering integer programs
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Improved approximation algorithms for geometric set cover
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Improved bound for the union of fat triangles
- Title not available (Why is that?)
- Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Approximation algorithms for covering/packing integer programs
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- On capacitated set cover problems
Cited In (52)
- A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
- 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
- On pseudo-disk hypergraphs
- Hitting sets when the shallow cell complexity is small
- Title not available (Why is that?)
- Approximation algorithm for minimum partial multi-cover under a geometric setting
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- 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
- PTAS for minimum cost multicovering with disks
- On tangencies among planar curves with an application to coloring L-shapes
- A PTAS for the horizontal rectangle stabbing problem
- Parallel algorithm for minimum partial dominating set in unit disk graph
- Exact and approximation algorithms for geometric and capacitated set cover problems
- Hypergraph representation via axis-aligned point-subspace cover
- Constant-factor approximation for TSP with disks
- 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
- A PTAS for the horizontal rectangle stabbing problem
- On the geometric set multicover problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- A PTAS for the Weighted Unit Disk Cover Problem
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- 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
- Weighted geometric set cover via quasi-uniform sampling
- Title not available (Why is that?)
- On capacitated set cover problems
- On Geometric Set Cover for Orthants
- 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
- 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
- Exact and approximation algorithms for geometric and capacitated set cover problems
- Geometric stabbing via threshold rounding and factor revealing LPs
- Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems
- Twin-width and polynomial kernels
- Multicommodity flow in trees: packing via covering and iterated relaxation
- On tangencies among planar curves with an application to coloring L-shapes
This page was built for publication: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743501)
