Packing and covering with non-piercing regions

DOI10.1007/s00454-018-9983-2zbMath1398.68659OpenAlexW2789583052MaRDI QIDQ1991095

Saurabh Ray, Sathish Govindarajan, Rajiv Raman, Aniket Basu Roy

Publication date: 30 October 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6359/

zbMATH Keywords

local searchdominating setapproximation algorithmsset covercapacitated packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (7)

On the geometric set multicover problem ⋮ Minimum power partial multi-cover on a line ⋮ On the geometric priority set cover problem ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Constructing planar support for non-piercing regions ⋮ Approximability of covering cells with line segments ⋮ A primal-dual algorithm for the minimum power partial cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Minimum vertex cover in rectangle graphs
• Improved results on geometric hitting set problems
• Hitting sets when the VC-dimension is small
• Label placement by maximum independent set in rectangles
• Almost optimal set covers in finite VC-dimension
• Independent set of intersection graphs of convex objects in 2D
• Geometric packing under non-uniform constraints
• Weighted geometric set cover via quasi-uniform sampling
• Guarding terrains via local search
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• New existence proofs ε-nets
• Fast approximation algorithms for a nonconvex covering problem
• A Separator Theorem for Planar Graphs
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation Schemes for Covering and Packing
• A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices

This page was built for publication: Packing and covering with non-piercing regions