Improved approximation algorithms for geometric set cover

DOI10.1007/S00454-006-1273-8zbMATH Open1106.68121OpenAlexW1999396007MaRDI QIDQ866970FDOQ866970

Authors: Kenneth L. Clarkson, Kasturi Varadarajan 

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

Recommendations

• Improved approximation algorithms for geometric set cover
• Faster approximation algorithms for geometric set cover
• Approximation algorithms for a geometric set cover problem
• Exact and approximation algorithms for geometric and capacitated set cover problems
• Exact and approximation algorithms for geometric and capacitated set cover problems
• An exact algorithm for a class of geometric set-cover problems
• scientific article; zbMATH DE number 2081015
• Near-linear algorithms for geometric hitting sets and set covers
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• scientific article; zbMATH DE number 7378687

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (83)

• On the set multicover problem in geometric settings
• On guarding orthogonal polygons with sliding cameras
• Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs
• Covering problem on fuzzy graphs and its application in disaster management system
• Algorithms for covering multiple submodular constraints and applications
• On partial covering for geometric set systems
• One-sided discrete terrain guarding and chordal graphs
• Small strong epsilon nets
• The parameterized complexity of stabbing rectangles
• A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
• An improved approximation algorithm for the most points covering problem
• Covering polygons with rectangles
• Approximation algorithms for polynomial-expansion and low-density graphs
• Improved results on geometric hitting set problems
• An algorithmic framework for solving geometric covering problems -- with applications
• Improved approximation algorithms for geometric set cover
• A fixed-parameter algorithm for guarding 1.5D terrains
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Approximation algorithms for art gallery problems in polygons
• On the union complexity of families of axis-parallel rectangles with a low packing number
• Near-linear time approximation schemes for geometric maximum coverage
• Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
• Weighted geometric set cover problems revisited
• Parameter analysis for guarding terrains
• TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS
• An improved line-separable algorithm for discrete unit disk cover
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Almost optimal set covers in finite VC-dimension
• Approximation algorithms for maximum independent set of pseudo-disks
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Survey of quantitative methods in construction
• Hitting sets online and unique-MAX coloring
• Clustering geometrically-modeled points in the aggregated uncertainty model
• A non-linear lower bound for planar epsilon-nets
• Faster approximation algorithms for geometric set cover
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Guarding a terrain by two watchtowers
• The class cover problem with boxes
• Approximation algorithms for a geometric set cover problem
• Domination in Geometric Intersection Graphs
• Helly-type theorems for approximate covering
• On the geometric set multicover problem
• The \(\varepsilon\)-\(t\)-net problem
• A PTAS for the Weighted Unit Disk Cover Problem
• On the approximability of covering points by lines and related problems
• On Geometric Set Cover for Orthants
• Geometric dominating-set and set-cover via local-search
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Title not available (Why is that?)
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Stabbing Convex Polygons with a Segment or a Polygon
• 1.5D terrain guarding problem parameterized by guard range
• Near-linear algorithms for geometric hitting sets and set covers
• Capacitated covering problems in geometric spaces
• Tight lower bounds for the size of epsilon-nets
• The number of holes in the union of translates of a convex set in three dimensions
• Approximately dominating representatives
• Exact and approximation algorithms for geometric and capacitated set cover problems
• A PTAS for the cardinality constrained covering with unit balls
• Small candidate set for translational pattern search
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• On the set multi-cover problem in geometric settings
• Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems
• The within-strip discrete unit disk cover problem
• Near-linear approximation algorithms for geometric hitting sets
• A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
• Helly-type theorems for approximate covering
• Altitude terrain guarding and guarding uni-monotone polygons
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Guarding 1.5D terrains with demands
• Constrained hitting set problem with intervals
• Improved Local Computation Algorithm for Set Cover via Sparsification
• Constant-factor approximation for TSP with disks
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Parameterized complexity of geometric covering problems having conflicts
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
• Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms
• One-sided terrain guarding and chordal graphs
• Capacitated covering problems in geometric spaces
• A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem
• Generalized class cover problem with axis-parallel strips
• Improved algorithms for minimum-membership geometric set cover
• Minimum-membership geometric set cover, revisited

Uses Software

• Hull

This page was built for publication: Improved approximation algorithms for geometric set cover

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