Usage
• 5 views

# Improved approximation algorithms for Min-Max Tree Cover, Bounded Tree Cover, Shallow-Light and Buy-at-Bulk k-Steiner Tree, and (k, 2)-Subgraph

• Author / Creator
• 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 ﬁnd 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 ﬁnd 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 ﬁnd 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 ﬁnd 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 ﬁ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 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].

• Subjects / Keywords
2011-11
• Type of Item
Thesis
• Degree
Master of Science
• DOI
https://doi.org/10.7939/R3GB1XT6V
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial 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.
• Language
English
• Institution
University of Alberta
• Degree level
Master's
• Department
• Department of Computing Science
• Supervisor / co-supervisor and their department(s)