Approximating corridors and tours via restriction and relaxation techniques
Arturo González-Gutiérrez, Teofilo F. Gonzalez · ACM Transactions on Algorithms · 2010
Given a rectangular boundary partitioned into rectangles, the Minimum-Length Corridor (MLC-R) problem consists of finding a corridor of least total length. A corridor is a set of connected line segments, each of which must lie along the line segments that form the rectangular boundary and/or the boundary of the rectangles, and must include at least one point from the boundary of every rectangle and from the rectangular boundary. The MLC-R problem is known to be NP-hard. We present the first polynomial-time constant ratio approximation algorithm for the MLC-R and MLC k problems. The MLC k problem is a generalization of the MLC-R problem where the rectangles are rectilinear c -gons, for c ≤ k and k is a constant. We also present the first polynomial-time constant ratio approximation algorithm for the Group Traveling Salesperson Problem (GTSP) for a rectangular boundary partitioned into rectilinear c -gons as in the MLC k problem. Our algorithms are based on the restriction and relaxation approximation techniques.