Konstantin Andreev
Approximation algorithms for network design and graph partitioning problems
Time: 10:30 a.m. on Tuesday, December 20th
Location: NSH 3305
Abstract:
Optimizing and efficiently using the bandwidth in a computer system is an important step in trying to improve the system’s performance. This thesis looks at three problems motivated by real world challenges. The over-riding theme in these analytical models is choosing locations and paths to provide service under various constraints and objectives.
The first example is the reliable delivery of live multimedia streams over the Internet. One of the most appealing applications of the Internet is the delivery of high-quality live audio and video streams to the desktop at low cost. The traditional centralized approach to delivering live streams suffers from well known scalability and reliability issues. Therefore the need for a distributed infrastructure consisting of a large number of servers deployed across the Internet arises. The purpose of a streaming overlay network is to transport bits from the encoder to the end user in a manner that alleviates the bottlenecks and takes care of connection losses. The overlay network studied in my thesis consists of three types of components, each globally distributed across the Internet. We assume that the loss rate between any pair of nodes in the network is known, and losses between different pairs are independent, but show extensions in which some losses may be correlated. We present a polynomial time approximation algorithm for this problem. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost within a logarithmic factor.
The second example is my work on simultaneous source location. At the design level we addressed the problem of choosing a set of sources in a general network in such a way that a given set of demands can be satisfied. We called this problem simultaneous source location. We gave an exact algorithm for trees using a dynamic programming approach. We show how this algorithm can be combined with a result of Harald Raecke to give a solution that has the exact number of nodes, but can exceed edge capacities by at most a polylogarithmic factor. We also investigated this problem for a graph of bounded treewidth. Many graphs arising from natural applications have bounded treewidth and problems that are in general intractable can be solved in polynomial time when restricted to graphs of bounded treewidth. We showed that simultaneous source location is NP-hard even on graphs of bounded treewidth. However we showed that one can design an efficient approximation algorithm. We gave a polynomial time approximation scheme (PTAS) with at most a $1+\epsilon$ violation of capacities, where can be made arbitrary small. We also showed a PTAS with exact capacities and $\tau+1$-approximation on the number of sources, where $\tau$ is the treewidth of the graph.
The third problem I considered is a question that is related to the management of communication links and arises in areas like parallel computing and chip design. The definition of the $k$-balanced graph partitioning problem is to divide the vertices of a graph into $k$ almost equal size components so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an $O(\log^{3/2} n)$-approximation. We also show a hardness of approximation result.
