An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection

摘要

Given an undirected graph G = (V, E) with |V| = n and |E| = m, nonnegative integers c(e) and d(e) for each edge e is an element of E, and a bound D, the constrained minimum spanning tree problem (CST) is to find a spanning tree T = (V, E-T) such that (Sigmaeis an element ofET) d(e) less than or equal to D and (Sigmaeis an element ofET) c(e) is minimized. We present an efficient polynomial time approximation scheme (EPTAS) for this problem. Specifically, for every is an element of > 0 we present a (1 + is an element of)-approximation algorithm with time complexity O((1/is an element of)(O(1/is an element of)) n(4)). Our method is based on Lagrangian relaxation and matroid intersection.