Weighted geometric set cover problems revisited

DOI10.20382/JOCG.V3I1A4MaRDI QIDQ2968086zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled, Mira Lee

Publication date 9 March 2017

Full work available at URL https://dblp.uni-trier.de/db/journals/jocg/jocg3.html#Har-PeledL12

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Recommendations

• PTAS for weighted set cover on unit squares
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Weighted geometric set multi-cover via quasi-uniform sampling
• Improved approximation algorithms for geometric set cover
• Weighted geometric set multi-cover via quasi-uniform sampling

Cited in

(21)

• Capacitated covering problems in geometric spaces
• scientific article; zbMATH DE number 6815827 (Why is no real title available?)
• Multi cover of a polygon minimizing the sum of areas
• Weighted geometric set cover via quasi-uniform sampling
• A PTAS for the Weighted Unit Disk Cover Problem
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• On the line-separable unit-disk coverage and related problems
• Weighted geometric set cover with rectangles of bounded integer side lengths
• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• Geometric dominating-set and set-cover via local-search
• Improved bounds for metric capacitated covering problems
• PTAS for minimum cost multicovering with disks
• Capacitated covering problems in geometric spaces
• A PTAS for the cardinality constrained covering with unit balls
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Weighted geometric set multi-cover via quasi-uniform sampling
• On the geometric priority set cover problem
• PTAS for weighted set cover on unit squares

This page was built for publication: Weighted geometric set cover problems revisited

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