The Constrained Minimum Spanning Tree Problem.pdf.pdf' (206.09 kB)
The Constrained Minimum Spanning Tree Problem
journal contributionposted on 1984-01-01, 00:00 authored by Ramamoorthi RaviRamamoorthi Ravi, M. X. Goemans
Given an undirected graph with two different nonnegative costs associated with every edge e (say, we for the weight and l e for the length of edge e) and a budget L, consider the problem of finding a spanning tree of total edge length at most L and minimum total weight under this restriction. This constrained minimum spanning tree problem is weakly NP-hard. We present a polynomial-time approximation scheme for this problem. This algorithm always produces a spanning tree of total length at most (1 + ε)L and of total weight at most that of any spanning tree of total length at most L, for any fixed ε >0. The algorithm uses Lagrangean relaxation, and exploits adjacency relations for matroids.