A PTAS for the horizontal rectangle stabbing problem
type: Item
instance of: scholarly article
title: A PTAS for the horizontal rectangle stabbing problem
zbMATH Open document ID: 1497.90176
DOI: 10.1007/978-3-031-06901-7_27
author: Arindam Khan
author: Aditya Subramanian
author: Andreas Wiese
publication date: 2022-08-16T00:00:00Z
full work available at URL: https://arxiv.org/abs/2111.05197
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7572301
zbMATH Keywords: geometric optimization
zbMATH Keywords: approximation algorithms
zbMATH Keywords: line stabbing
zbMATH Keywords: rectangles
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3214707727
cites work: Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
cites work: Latency-constrained aggregation in sensor networks
cites work: Almost optimal set covers in finite VC-dimension
cites work: Stabbing rectangles by line segments -- how decomposition reduces the shallow-cell complexity
cites work: Exact algorithms and APX-hardness results for geometric packing and covering problems
cites work: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Approximating the generalized minimum Manhattan network problem
cites work: Batch processing with interval graph compatibilities between tasks
cites work: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
cites work: Approximation schemes for covering and packing problems in image processing and VLSI
cites work: On Guillotine Separability of Squares and Rectangles.
cites work: Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
cites work: Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
cites work: Weighted geometric set cover via quasi-uniform sampling
Recommended article: Approximation Algorithms for Capacitated Rectangle Stabbing
Recommended article: Constant approximation algorithms for rectangle stabbing and related problems
Recommended article: Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
Recommended article: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
Recommended article: The parameterized complexity of stabbing rectangles
description: scientific article; zbMATH DE number 7572301