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
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
