ERA

Download the full-sized PDF of Improved approximation algorithms for Min-Max Tree Cover, Bounded Tree Cover, Shallow-Light and Buy-at-Bulk k-Steiner Tree, and (k, 2)-SubgraphDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3GB1XT6V

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Improved approximation algorithms for Min-Max Tree Cover, Bounded Tree Cover, Shallow-Light and Buy-at-Bulk k-Steiner 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
2011-09-22T13:35:06Z
Graduation date
2011-11
Degree
Master of Science
Degree level
Master's
Abstract
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].
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
Date Modified
2014-04-25T00: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:20-06:00
Filename: thesis.pdf
Original checksum: 5f7fe5ba392ff532c67b6cf472bceffa
Well formed: true
Valid: true
Page count: 72
Activity of users you follow
User Activity Date