Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization

Also published as a journal article: Lecture Notes in Computer Science, 2006; 3887:745-756We give faster approximation algorithms for the generalization of two NP-hard spanning tree problems. First, we investigate the problem of minimizing the degree of minimum spanning forests. Fischer [3] has shown how to compute a minimum spanning tree of degree at most b Δ* + ⌈logbn⌉ in time O(n4+1/lnb) for any b>1, where Δ* is the value of an optimal solution. We model our generalization as a multi-objective optimization problem and give a deterministic algorithm that computes for each number of connected components a solution with the same approximation quality as the algorithm of Fischer and runs in time O(n3+1/lnb). After that, we take a multi-objective view on the problem of computing minimum spanning trees with nonuniform degree bounds, which has been examined by Könemann and Ravi [7]. Given degree bounds Bv for each vertex v ∈ V, we construct an algorithm that computes for each number of connected components a spanning forest in which each vertex v has degree O(Bv + log n) and whose weight is at most a constant times the weight of a minimum spanning forest obeying the degree bounds. The total runtime of our algorithm is O(n3+2/lnb) for an arbitrary constant b>1. Setting b=ek, k > 2/3 an arbitrary constant, the runtime is by a factor n3−2/k log n less than the given bound by Könemann and Ravi.Frank Neumann and Marco Laumann