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

DOI10.1016/J.DAM.2021.05.005MaRDI QIDQ2030243zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

exact algorithmLaguerre-Voronoi diagramgeometric set-cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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

Cites work

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

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 for the construction of an optimal cover for sets in three-dimensional Euclidean space
• Algorithms of optimal set covering on the planar R^2
• 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)