| In this thesis, we study three combinatorial optimization problems on graphs, motivated by classical problems in computer networks and parallel computing and give approximation algorithms for them.; The first of these is designing an overlay multicast network for streaming. We present a polynomial time approximation algorithm for these problem. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost to within a logarithmic factor. The class of networks that our algorithm applies to includes the one used by Akamai Technologies to deliver live media streams over the Internet. In particular, we analyze networks consisting of three stages of nodes. The nodes in the first stage are the sources where live streams originate. A source forwards each of its streams to one or more nodes in the second stage, which are called reflectors. A reflector can split an incoming stream into multiple identical outgoing streams, which are then sent on to nodes in the third and final stage, which are called the sinks. As the packets in a stream travel from one stage to the next, some of them may be lost. The job of a sink is to combine the packets from multiple instances of the same stream (by reordering packets and discarding duplicates) to form a single instance of the stream with minimal loss. We assume that the loss rate between any pair of nodes in the network is known, and that losses between different pairs are independent, but discuss extensions in which some losses may be correlated.; The second problem is simultanious source location. The problem is selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied. We give an exact algorithm for trees and show how this can be combined with a result of Racke to give a solution that exceeds edge capacities by at most O(log2 n log log n), where n is the number of nodes. On graphs of bounded treewidth, we show the problem is still NP -Hard, but we are able to give a PTAS with at most O(1 + epsilon) violation of the capacities, or a (k + 1)-approximation with exact capacities, where k is the treewidth and epsilon can be made arbitrarily small.; The third problem is (k, nu)-balanced graph partitioning. (Abstract shortened by UMI.)... |
