Improved approximation algorithms for geometric set cover
From MaRDI portal
Publication:866970
DOI10.1007/s00454-006-1273-8zbMath1106.68121OpenAlexW1999396007MaRDI QIDQ866970
Kasturi R. Varadarajan, Kenneth L. Clarkson
Publication date: 14 February 2007
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-006-1273-8
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (71)
Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ One-sided discrete terrain guarding and chordal graphs ⋮ On the union complexity of families of axis-parallel rectangles with a low packing number ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Survey of quantitative methods in construction ⋮ Covering problem on fuzzy graphs and its application in disaster management system ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem ⋮ On the geometric set multicover problem ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Approximately dominating representatives ⋮ Improved results on geometric hitting set problems ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Small strong epsilon nets ⋮ Capacitated covering problems in geometric spaces ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ Geometric dominating-set and set-cover via local-search ⋮ The class cover problem with boxes ⋮ The parameterized complexity of stabbing rectangles ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ On the approximability of covering points by lines and related problems ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ One-sided terrain guarding and chordal graphs ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Constrained hitting set problem with intervals ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Covering Polygons with Rectangles ⋮ Stabbing Convex Polygons with a Segment or a Polygon ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Helly-type theorems for approximate covering ⋮ Guarding 1.5D terrains with demands ⋮ 1.5D terrain guarding problem parameterized by guard range ⋮ Geometric hitting set for segments of few orientations ⋮ AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER ⋮ The number of holes in the union of translates of a convex set in three dimensions ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ The within-strip discrete unit disk cover problem ⋮ An improved approximation algorithm for the most points covering problem ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Guarding a terrain by two watchtowers ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Domination in Geometric Intersection Graphs ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ On Geometric Set Cover for Orthants ⋮ Hitting sets online and unique-MAX coloring ⋮ Unnamed Item ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Approximability of covering cells with line segments ⋮ On Partial Covering For Geometric Set Systems ⋮ Altitude terrain guarding and guarding uni-monotone polygons ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ Small candidate set for translational pattern search ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs ⋮ Unnamed Item ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model ⋮ TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS ⋮ A fixed-parameter algorithm for guarding 1.5D terrains ⋮ Parameter analysis for guarding terrains
Uses Software
This page was built for publication: Improved approximation algorithms for geometric set cover
