Abstract
Approximation Algorithms for the Minimum-Length Corridor and Related Problems
by: Arturo Gonzalez-Gutierrez and Teofilo F. Gonzalez
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.
Keywords:
Approximation algorithms, restriction-relaxation techniques, minimum length corridors, polynomial time, GTSP
Date:
May 2007
Document: 2007-03
