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.

122 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu