A PTAS for the horizontal rectangle stabbing problem

DOI10.1007/S10107-024-02106-YMaRDI QIDQ6589763zbMATH OpenFDO

Authors Arindam Khan, Aditya Subramanian, Andreas Wiese

Publication date 20 August 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10107-024-02106-Y

zbMATH Keywords

approximation algorithmsgeometric optimizationrectanglesstabbing

Mathematics Subject Classification ID

Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A (2+)-approximation algorithm for the storage allocation problem
• A (5/3+)-approximation for strip packing
• A Greedy Heuristic for the Set-Covering Problem
• A PTAS for packing hypercubes into a knapsack
• A PTAS for the horizontal rectangle stabbing problem
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• Almost optimal set covers in finite VC-dimension
• Approximating the generalized minimum Manhattan network problem
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• Approximation and online algorithms for multidimensional bin packing: a survey
• Approximation schemes for covering and packing problems in image processing and VLSI
• Batch processing with interval graph compatibilities between tasks
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Dynamic Geometric Set Cover and Hitting Set
• Dynamic geometric set cover, revisited
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Geometry meets vectors: approximation algorithms for multidimensional packing
• Improved approximation algorithm for two-dimensional bin packing
• Latency-constrained aggregation in sensor networks
• On Guillotine Separability of Squares and Rectangles.
• Online and dynamic algorithms for geometric set cover and hitting set
• Peak Demand Minimization via Sliced Strip Packing.
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Small-size -nets for axis-parallel rectangles and boxes
• Stabbing rectangles by line segments -- how decomposition reduces the shallow-cell complexity
• The geometry of scheduling
• Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items
• Tight approximation algorithms for two-dimensional guillotine strip packing
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling

This page was built for publication: A PTAS for the horizontal rectangle stabbing problem

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