An exact algorithm for a class of geometric set-cover problems

DOI10.1016/J.DAM.2021.05.005zbMATH Open1469.90121OpenAlexW3163918205MaRDI QIDQ2030243FDOQ2030243

Authors: Claudio Contardo, Alain Hertz 

Publication date: 7 June 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.05.005

Recommendations

• On covering bounded sets by collections of circles of various radii
• Unit disk cover problem in 2D
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Algorithms of optimal set covering on the planar R^2
• scientific article; zbMATH DE number 1522573

zbMATH Keywords

exact algorithmLaguerre-Voronoi diagramgeometric set-cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• An improved line-separable algorithm for discrete unit disk cover
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• On the discrete unit disk cover problem
• Covering Points by Unit Disks of Fixed Location
• Improved results on geometric hitting set problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Unit disk cover problem in 2D
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Optimal packing and covering in the plane are NP-complete
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry
• The Continuous-Time Service Network Design Problem
• A sampling-based exact algorithm for the solution of the minimax diameter clustering problem
• A scalable exact algorithm for the vertex \(p\)-center problem

Cited In (12)

• Improved approximation algorithms for geometric set cover
• Disc covering problem with application to digital halftoning
• Improved approximation algorithms for geometric set cover
• Weighted geometric set cover with rectangles of bounded integer side lengths
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• An exact algorithm for the maximal covering problem
• Algorithms of optimal set covering on the planar R^2
• Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space
• Geometric dominating-set and set-cover via local-search
• Covering a set of points with a minimum number of equal disks via simulated annealing
• The Exact Subset MultiCover problem
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

This page was built for publication: An exact algorithm for a class of geometric set-cover problems

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