 5 views
 1 download
Improved approximation algorithms for MinMax Tree Cover, Bounded Tree Cover, ShallowLight and BuyatBulk kSteiner Tree, and (k, 2)Subgraph

 Author / Creator
 Khani, Mohammad Reza

In this thesis we provide improved approximation algorithms for the MinMax kTree Cover, Bounded Tree Cover and ShallowLight kSteiner Tree, (k, 2)subgraph problems. In Chapter 2 we consider the MinMax 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 ﬁnd a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3approximation 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 APXhardness 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 ﬁnd a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5approximation algorithm for BTC, improving the 3approximation bound in [7]. In Chapter 4 we consider the ShallowLight k Steiner Tree (SLk ST) problem. In the boundeddiameter or shallowlight 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 ﬁnd a minimum ccost rrooted Steiner tree containing at least k terminals whose diameter under l metric is at most L. The input to the BuyatBulk kSteiner 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 ﬁnd a minimum total cost rrooted 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 ﬁnds 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 ﬁnding a minimum cost 2edgeconnected subgraph with at least k vertices, which is introduced as the (k, 2)subgraph problem in [94] (STOC’07/SICOMP09). This generalizes some wellstudied classical problems such as the k MST and the minimum cost 2edgeconnected subgraph problems. We give an O(log n) approximation algorithm for this problem which improves upon the O(log2 n)approximation of [94].

 Graduation date
 201111

 Type of Item
 Thesis

 Degree
 Master of Science

 License
 This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for noncommercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.