Andréa Werneck Richa

On Distributed Network Resource Allocation Degree Type: Ph.D. in Algorithms, Combinatorics and Optimization
Advisor(s): Bruce Maggs
Graduated: August 1998

Abstract:

This thesis addresses several resource allocation problems that arise in the context of distributed networks. First, we present a scheme for accessing shared copies of objects in a network that has asymptotically optimal expected cost per access for a class of cost functions that captures the hierarchical structure of most wide-area networks. Second, we present an off-line polynomial-time algorithm that finds an asymptotically optimal schedule for the movement of packets whose paths through a network have already been determined. This is an improvement on a previous result by Leighton, Maggs, and Rao, who proved the existance of such schedules; their proof, however, was not constructive. Finally we present a polynomial-time O(log n)-approximation algorithm for finding an embedding of a network with nprocessors into an n-node linear array so as to minimize the weighted sum of the edge dilations -- i.e., for the minimum linear arrangement problem. This problem is NP-hard, and the previous best approximation bound known was O(log n log log n). In the case of planar networks, we bring the approximation factor down to O(log log n). We also extend our approximation techniques to the minimum storage-time product and the minimum containing interval graph problem.

Thesis Committee:
Bruce M. Maggs (Chair)
Alan Frieze
R. Ravi
Greg C. Plaxton (Univ. of Texas at Austin)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Distributed network, resource allocation, approximation algorithm, randomized algorithm, shared object, wide-area network, hierarchical model, expected cost, packet routing, scheduling, Lovasz Local Lemma, optimal schedule, network emulation, embedding, congestion, dilation, ordering, linear arrangement, linear array, combinatorial optimization, interval graph, storage-time product, spreading metric, planar graph