Approximation of rectangle stabbing and interval stabbing problems

DOI10.1007/978-3-540-30140-0_39MaRDI QIDQ5464600zbMATH OpenOpenAlexFDO

Authors Sofia Kovaleva, Frits C. R. Spieksma

Publication date 18 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100428

Mathematics Subject Classification ID

Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• Constant approximation algorithms for rectangle stabbing and related problems
• Approximation Algorithms for Capacitated Rectangle Stabbing
• Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem

Cited in

(8)

• Stabbing isothetic boxes and rectangles in \(O(n\log n)\) time
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Interval Stabbing Problems in Small Integer Ranges
• Partial multicovering and the d-consecutive ones property
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• Geometric stabbing via threshold rounding and factor revealing LPs
• Algorithms for high dimensional stabbing problems

This page was built for publication: Approximation of rectangle stabbing and interval stabbing problems

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