Approximation Algorithms for the Minimum-Length Corridor and Related Problems

Report ID: 
2007-03
Authors: 
Arturo Gonzalez-Gutierrez and Teofilo F. Gonzalez
Date: 
2007-05-01 05:00:00

Abstract

Given a rectangular boundary partitioned into rectangles, the Minimum-Length Corridor (MLC-R) problem consists of nding 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 MLC_n problems. The MLC_n problem is a generalization of the MLC-R problem where the rectangles are rectilinear k-gons, for k <= n and n is a constant. We also present a polynomial time constant ratio approximation algorithm for the Group Traveling Salesperson Problem (GTSP) for a rectangular boundary partitioned into rectilinear k-gons as in the MLC_n problem.

Document

PDF icon 2007-03.pdf