ABSTRACT

In the current chapter, we examine complexity issues and approximation algorithms for the Minimum-Length Corridor (MLC) problem and its variants. These problems have applications in several fields of study including VLSI (Very Large Scale Integration) routing, transportation systems, and so on. Specifically, we discuss the NP-hardness (Nondeterministic Polynomial time-hardness) of the MLC problem and present a hierarchy of related problems, most of which remain NP-hard. We present a general framework for a class of polynomial-time constant ratio-approximation algorithms for the MLC-R, which is the MLC problem in which all the objects are rectangles. The approximation algorithms are based on the restriction and relaxation methodologies. Finally, we present new experimental analysis of our approximation algorithms for families of problem instances.