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

  Khani, Mohammad Reza

• 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 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. 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

  • CombinatorialOptimization
  • Theory of Computation
  • Approximation Algorithms
  • Hardness of Approximation

• Graduation date

  Fall 2011

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3GB1XT6V

• License

  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.