Minimum-length corridors: complexity and approximations
Teofilo F. Gonzalez, Arturo González-Gutiérrez · 2007
The Minimum-Length Corridor (MLC) problem and some of its variants are studied. Given a rectangular boundary partitioned into rectilinear polygons (rooms), the MLC problem is to find 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 rooms, and must include at least one point from every room and from the rectangular boundary. The NP-completeness of the decision version of the MLC problem even when it is restricted to a rectangular boundary partitioned into rectangles is established. We call this restricted version the MLC-R problem. In virtue of these results, we present a parameterized algorithm Alg(S) for the MLC-R problem, where S is a selector function. For certain selector functions, Alg( S) results in the first provably polynomial time approximation algorithm for the MLC-R problem with a constant approximation ratio. Algorithm Alg(S) restricts the solution space by limiting in each room the possible vertices, from which at least one must be part of the corridor. The resulting problem, which remains NP-complete, is solved by relaxing the set of feasible solutions. Then the solution is rounded and solves the original problem instance. This approach is adapted to the rectangular group-TSP, resulting in a constant ratio approximation algorithm. The approximation scheme can also be applied to the MLCk problem, i.e., the MLC problem when every room is a rectilinear c-gon, for c ≥ k, but the approximation ratio depends on k. A polynomial time constant ratio approximation algorithm for the group-TSP for a rectangular boundary partitioned into rectilinear c-gons, as in the MLCk problem when k is a constant, is presented. An application for the MLC problem is when laying optical fiber in metropolitan areas and every block (or set of blocks) is connected through its own gateway. The objective is to find a minimum-length corridor connecting all the gateways in the area. Corridor problems also have applications in VLSI and floorplanning when laying wires for clock signals or power, and wires for electrical networks, or optical fibers for data communications.