Approximation algorithms for a geometric set cover problem

DOI10.1016/J.DAM.2011.11.023MaRDI QIDQ423912zbMATH OpenOpenAlexFDO

Authors Valentin E. Brimkov, Michael Mastroianni, Andrew Leach, Jimmy Wu

Publication date 30 May 2012

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

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

zbMATH Keywords

approximation algorithmset coververtex coverart-gallery problemguarding set of segments

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Approximation algorithms (68W25)

Recommendations

• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Approximability issues of guarding a set of segments
• Covering a Set of Points with a Minimum Number of Lines
• scientific article; zbMATH DE number 3888915

Cites work

• scientific article; zbMATH DE number 1670858 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 3225844 (Why is no real title available?)
• scientific article; zbMATH DE number 3102025 (Why is no real title available?)
• An Algorithm for a Minimum Cover of a Graph
• Experimental study on approximation algorithms for guarding sets of line segments
• Guarding a set of line segments in the plane
• Modem illumination of monotone polygons
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

Cited in

(21)

• Universal approximations for TSP, Steiner tree, and set cover
• Improved approximation algorithms for geometric set cover
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• scientific article; zbMATH DE number 7376034 (Why is no real title available?)
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• Improved approximation algorithms for geometric set cover
• scientific article; zbMATH DE number 784428 (Why is no real title available?)
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Approximability issues of guarding a set of segments
• Experimental study on approximation algorithms for guarding sets of line segments
• Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Algorithms of optimal set covering on the planar R^2
• On the approximability of covering points by lines and related problems
• Intersections and circuits in sets of line segments
• Geometric dominating-set and set-cover via local-search
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Covering a Set of Points with a Minimum Number of Lines
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Dispersion with connectivity in wireless mesh networks

This page was built for publication: Approximation algorithms for a geometric set cover problem

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