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.
Exact and Approximate Algorithms for
Assignment Problems in Distributed Systems
David Fernandez-Baca and Anand Medepalli
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
Keywords: Computer networks, distributed systems, dynamic programming,
knapsack problems, scheduling, task allocation.
Contact site administrator at: firstname.lastname@example.org