Improved approximation algorithms for Min-Max Tree Cover, Bounded Tree Cover, Shallow-Light and Buy-at-Bulk k-Steiner Tree, and (k, 2)-Subgraph
Khani, Mohammad Reza · 2011
In this thesis we provide improved approximation algorithms for the Min-Max k-Tree Cover, Bounded Tree Cover and Shallow-Light k-Steiner Tree, (k, 2)-subgraph problems. In Chapter 2 we consider the Min-Max k -Tree Cover (MMkTC). Given a graph G = (V, E ) with weights w: E → Z+ , a set T1, T2, ... , Tk of subtrees of G is called a tree cover of G if V = U V(Ti). In the MMkTC problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for MMkTC improving the two different approximation algorithms presented in [7,46] with ratios 4 and (4+e). The problem is known to have an APX-hardness lower bound of 3/2[125]. In Chapter 3 we consider the Bounded Tree Cover (BTC) problem. In the BTC problem we are given a graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5-approximation algorithm for BTC, improving the 3-approximation bound in [7]. In Chapter 4 we consider the Shallow-Light k -Steiner Tree (SLk ST) problem. In the bounded-diameter or shallow-light k -Steiner tree problem , we are given a graph G = (V, E ) with terminals T ⊆ V containing a root r ∈ T , a cost function c : E → Q+ , a length function l: E → Q+ , a bound L > 0 and an integer k ≥ 1. The goal is to find a minimum c-cost r-rooted Steiner tree containing at least k terminals whose diameter under l metric is at most L. The input to the Buy-at-Bulk k-Steiner tree problem (BBkST) is similar: graph G = (V, E), terminals T ⊆ V , cost and length functions c,l:E→ Q+ , and an integer k ≥ 1. The goal is to find a minimum total cost r-rooted Steiner tree H containing at least k terminals, where the cost of each edge e is c(e)+l(e)·f (e) where f (e) denotes the number of terminals whose path to root in H contains edge e. We present a bicriteria (O(log^2 n), O(logn))-approximation for SLkST: the algorithm finds a k -Steiner tree of diameter at most O(L · log n) whose cost is at most O(log^2 n · opt∗ ) where opt∗ is the cost of an LP relaxation of the problem. This improves on the algorithm of [66] (APPROX’06/Algorithmica’09) which had ratio (O(log^4 n), O(log^2 n)). Using this, we obtain an O(log^3 n)-approximation for BBk ST, which improves upon the O(log^4 n)-approximation of [66]. Finally, we show our approximation algorithm for BBkST implies approximation factors for some other network design problems. In Chapter 5 we consider the problem of finding a minimum cost 2-edge-connected sub-graph with at least k vertices, which is introduced as the (k, 2)-subgraph problem in [94] (STOC’07/SICOMP09). This generalizes some well-studied classical problems such as the k -MST and the minimum cost 2-edge-connected subgraph problems. We give an O(log n)- approximation algorithm for this problem which improves upon the O(log2 n)-approximation of [94].