Weighted geometric set cover problems revisited

DOI10.20382/JOCG.V3I1A4zbMATH Open1404.68192OpenAlexW1870040444MaRDI QIDQ2968086FDOQ2968086

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

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

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)

Cited In (20)

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

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)