Approximation algorithms for a geometric set cover problem

DOI10.1016/J.DAM.2011.11.023zbMATH Open1253.68358OpenAlexW2049234398MaRDI QIDQ423912FDOQ423912

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the ratio of optimal integral and fractional covers
• On the hardness of approximating minimization problems
• An Algorithm for a Minimum Cover of a Graph
• 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
• Guarding a set of line segments in the plane

Cited In (20)

• Improved approximation algorithms for geometric set cover
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved approximation algorithms for geometric set cover
• Geometric hitting set for segments of few orientations
• Title not available (Why is that?)
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Approximability issues of guarding a set of segments
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• 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
• Approximability of covering cells with line segments
• 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
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Dispersion with connectivity in wireless mesh networks
• Universal approximations for TSP, Steiner tree, and set cover

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)