Approximation Algorithms for the Minimum-Length Corridor and Related Problems.
Arturo González-Gutiérrez, Teofilo F. Gonzalez · 2007
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 has been shown to be NP-hard. In this paper we present the first polynomial time constant ratio approximation algorithm for the MLC-R and MLCn problems. The MLCn problem is a generalization of the the MLC-R problem where the rectangles are rectilinear k-gons, for k ≤ n. We also present a polynomial time constant ratio approximation algorithm for the Group Traveling Salesperson Problem (GTSP) for a rectangle partitioned into rectilinear k-gons as in the MLCn problem.