Approximation algorithms for hitting objects with straight lines
From MaRDI portal
Publication:1173978
DOI10.1016/0166-218X(91)90011-KzbMath0800.68619MaRDI QIDQ1173978
Publication date: 25 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (27)
On the Approximability of Orthogonal Order Preserving Layout Adjustment ⋮ covering grid points in a convex polygon with straight lines∗ ⋮ Hypergraph representation via axis-aligned point-subspace cover ⋮ Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ Guarding orthogonal art galleries with sliding cameras ⋮ On fair covering and hitting 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 ⋮ Optimal Insertion of a Segment Highway in a City Metric ⋮ The parameterized complexity of stabbing rectangles ⋮ Improved parameterized algorithms for minimum link-length rectilinear spanning path problem ⋮ Cutting polygons into small pieces with chords: Laser-based localization ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Geometric hitting set for segments of few orientations ⋮ Traversing a set of points with a minimum number of turns ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ On a minimum linear classification problem ⋮ Parameterized Complexity of Stabbing Rectangles and Squares in the Plane ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ On Covering Points with Minimum Turns ⋮ SEPARATING POINTS BY AXIS-PARALLEL LINES ⋮ On the shortest separating cycle ⋮ Latency Constrained Aggregation in Chain Networks Admits a PTAS ⋮ APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of polyhedral separability
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- On the complexity of locating linear facilities in the plane
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
This page was built for publication: Approximation algorithms for hitting objects with straight lines
