Capacitated Covering Problems in Geometric Spaces

DOI10.4230/LIPIcs.SoCG.2018.7zbMath1489.68337OpenAlexW2772875134MaRDI QIDQ5115774

Santanu Bhowmick, Tanmay Inamdar, Sayan Bandyapadhyay, Kasturi R. Varadarajan

Publication date: 18 August 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.7

zbMATH Keywords

LP roundinggeometric set coverbi-criteria approximationcapacitated covering

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Switching to directional antennas with constant increase in radius and hop distance
• Improved results on geometric hitting set problems
• LP-based approximation algorithms for capacitated facility location
• Improved approximation algorithms for geometric set cover
• Centrality of trees for capacitated \(k\)-center
• Capacitated domination problems on planar graphs
• Exact and approximation algorithms for geometric and capacitated set cover problems
• An analysis of the greedy algorithm for the submodular set covering problem
• Almost optimal set covers in finite VC-dimension
• Replica placement on bounded treewidth graphs
• A PTAS for the cardinality constrained covering with unit balls
• Polynomial time approximation schemes for base station coverage with minimum total radii
• An improved approximation algorithm for vertex cover with hard capacities
• Weighted geometric set cover via quasi-uniform sampling
• WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
• LP-Based Algorithms for Capacitated Facility Location
• Covering Problems with Hard Capacities
• Approximation schemes for covering and packing problems in image processing and VLSI
• Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
• How to Allocate Network Centers
• The Capacitated K-Center Problem
• Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
• Iterative Partial Rounding for Vertex Cover with Hard Capacities
• Packing and Covering with Non-Piercing Regions
• Analytical approach to parallel repetition
• On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes

This page was built for publication: Capacitated Covering Problems in Geometric Spaces