Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
From MaRDI portal
Publication:5757391
DOI10.1137/S089548010444273XzbMath1127.68117MaRDI QIDQ5757391
Frits C. R. Spieksma, Sofia Kovaleva
Publication date: 6 September 2007
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (13)
A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand ⋮ 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 ⋮ The parameterized complexity of stabbing rectangles ⋮ Guarding 1.5D terrains with demands ⋮ Geometric hitting set for segments of few orientations ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Unnamed Item ⋮ Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
This page was built for publication: Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
