Files in this item
Files  Description  Format 

application/pdf 1_Korula_Nitish.pdf (1MB)  (no description provided) 
Description
Title:  Approximation Algorithms for Network Design and Orienteering 
Author(s):  Korula, Nitish J. 
Director of Research:  Chekuri, Chandra S. 
Doctoral Committee Chair(s):  Chekuri, Chandra S. 
Doctoral Committee Member(s):  Erickson, Jeff G.; HarPeled, Sariel; Gupta, Anupam 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Algorithms
Approximation algorithms Network design Graph algorithms Connectivity Orienteering 
Abstract:  This thesis presents approximation algorithms for some NPHard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widelybelieved complexitytheoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomialtime) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NPHard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible. The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing faulttolerant networks. Two vertices u,v in a network are said to be kedgeconnected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are kvertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below. We study the problem of building 2vertexconnected networks that are large and have low cost. Given an nnode graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimumcost 2vertexconnected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2vertexconnected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2vertexconnected graph, finds a 2vertexconnected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications. Recent breakthroughs on vertexconnectivity have made use of algorithms for elementconnectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise elementconnectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and nonterminal vertices; such problems have applications in VLSI design and other areas. We also use this reduction algorithm to analyze simple algorithms for singlesink network design problems with high vertexconnectivity requirements; we give an O(k log n)approximation for the problem of kconnecting a given set of terminals to a common sink. We study similar problems in which different types of links, of varying capacities and costs, can be used to connect nodes; assuming there are economies of scale, we give algorithms to construct lowcost networks with sufficient capacity or bandwidth to simultaneously support flow from each terminal to the common sink along many vertexdisjoint paths. We further investigate capacitated network design, where edges may have arbitrary costs and capacities. Given a connectivity requirement R_uv for each pair of vertices u,v, the goal is to find a lowcost network which, for each uv, can support a flow of R_uv units of traffic between u and v. We study several special cases of this problem, giving both algorithmic and hardness results. In addition to Network Design, we consider certain Traveling Salespersonlike problems, where the goal is to find short walks that visit many distinct vertices. We give a (2 + epsilon)approximation for Orienteering in undirected graphs, achieving the best known approximation ratio, and the first approximation algorithm for Orienteering in directed graphs. We also give improved algorithms for Orienteering with time windows, in which vertices must be visited between specified release times and deadlines, and other related problems. These problems are motivated by applications in the fields of vehicle routing, delivery and transportation of goods, and robot path planning. 
Issue Date:  20100820 
URI:  http://hdl.handle.net/2142/16731 
Rights Information:  Copyright 2010 Nitish John Korula. Previous versions of this work have been published in various conferences. Copyright on these versions is held by the respective publishers, (SIAM and SpringerVerlag), but authors retain the rights to use this content in future works such as survey articles, books, theses, etc. 
Date Available in IDEALS:  20100820 
Date Deposited:  201008 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science