On Distributed Network Resource Allocation
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 existence 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 n processors 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1998
- Accession Number
- ADA358569
Entities
People
- Andréa W. Richa
Organizations
- Carnegie Mellon University