Approximation algorithms for a geometric set cover problem

DOI10.1016/j.dam.2011.11.023zbMath1253.68358OpenAlexW2049234398MaRDI QIDQ423912

Michael Mastroianni, Valentin E. Brimkov, Jimmy Ming-Tai Wu, Andrew J. Leach

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 algorithmvertex coverset coverart-gallery problemguarding set of segments

Mathematics Subject Classification ID

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

Related Items (6)

On the approximability of covering points by lines and related problems ⋮ Dispersion with connectivity in wireless mesh networks ⋮ Geometric hitting set for segments of few orientations ⋮ Approximability of covering cells with line segments ⋮ Intersections and circuits in sets of line segments ⋮ Approximability issues of guarding a set of segments

Cites Work

• Guarding a set of line segments in the plane
• On the ratio of optimal integral and fractional covers
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• Modem illumination of monotone polygons
• Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments
• An Algorithm for a Minimum Cover of a Graph
• On the hardness of approximating minimization problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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