Improved approximation algorithms for MinMax Tree Cover, Bounded Tree Cover, ShallowLight and BuyatBulk kSteiner Tree, and (k, 2)Subgraph Open Access
Descriptions
 Other title
 Subject/Keyword

Theory of Computation
Approximation Algorithms
CombinatorialOptimization
Hardness of Approximation
 Type of item
 Thesis
 Degree grantor

University of Alberta
 Author or creator

Khani, Mohammad Reza
 Supervisor and department

Mohammad R. Salavatipour
 Examining committee member and department

Lorna Stewart (Computing Science)
Marek Reformat (Electrical and Computer Engineering)
 Department

Department of Computing Science
 Specialization

 Date accepted

20110922T13:35:06Z
 Graduation date

201111
 Degree

Master of Science
 Degree level

Master's
 Abstract

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].
 Language

English
 DOI

doi:10.7939/R3GB1XT6V
 Rights
 This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
 Citation for previous publication

File Details
 Date Uploaded
 20120313T16:16:54.268+00:00
 Date Modified
 20140425T00:17:53.150+00:00
 Audit Status
 Audits have not yet been run on this file.
 Characterization

File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 551799
Last modified: 2016:08:04 15:20:2006:00
Filename: thesis.pdf
Original checksum: 5f7fe5ba392ff532c67b6cf472bceffa
Well formed: true
Valid: true
Page count: 72
Activity of users you follow
User Activity 
Date 