archives

Exact and approximate Algorithms for Assignment Problems in Distributed Systems


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Fernandez-Baca, David and Medepalli, Anand (1992) Exact and approximate Algorithms for Assignment Problems in Distributed Systems. Technical Report TR92-29, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Exact and Approximate Algorithms for
Assignment Problems in Distributed Systems
by
David Fernandez-Baca and Anand Medepalli
TR92-29
Abstract
We present exact dynamic programming algorithms for two variants of the
task assignment problem on distributed systems:  (1) finding a
minimum-cost assignment when one of the processors has limited memory
and (2) finding an assignment that minimizes the maximum processor
load.  These procedures lead to approximation schemes for the case
where the communication graph is a partial $k$-tree.  In contrast to
these results, we show that, for arbitrary graphs, no fully polynomial
time approximation schemes exist unless P = NP.  Finally, we discuss
implementation details for our algorithms and summarize our
experimental results.
Keywords:  Computer networks, distributed systems, dynamic programming,
knapsack problems, scheduling, task allocation.

Subjects:All uncategorized technical reports
ID code:00000032
Deposited by:Staff Account on 16 October 1992



Contact site administrator at: ssg@cs.iastate.edu