Capacitated covering problems in geometric spaces

DOI10.4230/LIPICS.SOCG.2018.7MaRDI QIDQ5115774zbMATH OpenOpenAlexFDO

Authors Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, Kasturi Varadarajan

Publication date 18 August 2020

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

zbMATH Keywords

bi-criteria approximationcapacitated coveringgeometric set coverLP rounding

Mathematics Subject Classification ID

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

Recommendations

• Capacitated covering problems in geometric spaces
• On capacitated covering with unit balls
• Capacitated discrete unit disk cover
• Exact and approximation algorithms for geometric and capacitated set cover problems
• Exact and approximation algorithms for geometric and capacitated set cover problems

Cites work

• A PTAS for the cardinality constrained covering with unit balls
• Almost optimal set covers in finite VC-dimension
• An analysis of the greedy algorithm for the submodular set covering problem
• An improved approximation algorithm for vertex cover with hard capacities
• Analytical approach to parallel repetition
• Approximation schemes for covering and packing problems in image processing and VLSI
• Capacitated domination problems on planar graphs
• Centrality of trees for capacitated \(k\)-center
• Covering Problems with Hard Capacities
• Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
• Exact and approximation algorithms for geometric and capacitated set cover problems
• How to Allocate Network Centers
• Improved approximation algorithms for geometric set cover
• Improved results on geometric hitting set problems
• Iterative partial rounding for vertex cover with hard capacities
• LP-based algorithms for capacitated facility location
• LP-based approximation algorithms for capacitated facility location
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Packing and covering with non-piercing regions
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Replica placement on bounded treewidth graphs
• Small-size -nets for axis-parallel rectangles and boxes
• Switching to directional antennas with constant increase in radius and hop distance
• The Capacitated K-Center Problem
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover problems revisited
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(5)

• Capacitated covering problems in geometric spaces
• On capacitated covering with unit balls
• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• scientific article; zbMATH DE number 7651201 (Why is no real title available?)
• Energy-constrained geometric coverage problem

This page was built for publication: Capacitated covering problems in geometric spaces

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