Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
From MaRDI portal
Publication:3150279
DOI10.1006/jagm.2002.1221zbMath1005.68179OpenAlexW1994612875MaRDI QIDQ3150279
Daya Ram Gaur, Ramesh Krishnamurti, Toshihide Ibaraki
Publication date: 30 September 2002
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6f3a4a9656b5250187613f195f2ff8d6dae438ab
Related Items (29)
Approximation algorithms for orthogonal line centers ⋮ On the Approximability of Orthogonal Order Preserving Layout Adjustment ⋮ Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ On dominating set of some subclasses of string graphs ⋮ Partial multicuts in trees ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ The parameterized complexity of stabbing rectangles ⋮ A unified approach to approximating partial covering problems ⋮ Load-balancing spatially located computations using rectangular partitions ⋮ Covering segments with unit squares ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ Approximation algorithms for orthogonal line centers ⋮ Rounding to an integral program ⋮ Improved approximations for guarding 1.5-dimensional terrains ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Unnamed Item ⋮ Parameterized Complexity of Stabbing Rectangles and Squares in the Plane ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ SEPARATING POINTS BY AXIS-PARALLEL LINES ⋮ Covering and packing of rectilinear subdivision ⋮ On the shortest separating cycle ⋮ Latency Constrained Aggregation in Chain Networks Admits a PTAS ⋮ APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES
This page was built for publication: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
