File forwarding approximation algorithms.

Title: File forwarding approximation algorithms.
Identifier: AAI9521293
identifier: 9521293
Creator: Lord, Kenneth John.
Contributor: Adviser: Jennifer Whitehead
Date: 1995
Language: English
Publisher: City University of New York.
Subject: Computer Science
Abstract: The file transfer scheduling problem was introduced and studied by Coffman, Garey, Johnson and LaPaugh where it was shown that determining the optimal schedule where all file transfers are completed in minimal time is NP-Complete. This was extended by Whitehead to include the case of forwarded files. We examine polynomial-time approximation algorithms for the forwarding model where knowledge of the file transfer graph on the part of the individual nodes is local and global. We show that in the worst case the local algorithms of "List Scheduling" and "Farthest-First" yield polynomial approximations to the optimal length schedule. We also show randomized and deterministic algorithms that yield worst case polylogarithmic approximations to the optimal length schedule.
Type: dissertation
Source: PQT Legacy CUNY.xlsx
degree: Ph.D.