The Constrained Minimum Spanning Tree Problem.pdf.pdf' (206.09 kB)
0/0

The Constrained Minimum Spanning Tree Problem

Download (206.09 kB)
journal contribution
posted on 01.01.1984 by Ramamoorthi 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.

History

Date

01/01/1984

Exports