IEICE TRANSACTIONS on Fundamentals
Task Assignment in Homogeneous Linear Array Networks
Summary :
This letter deals with the problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. Recently, an optimal algorithm with the time complexity of O(n2m3 log n) has been suggested for the problem of assigning m interacting tasks to a linear array of n processors. They solved the problem by using the two-terminal network flow approach. In this letter, we propose a multiterminal network flow approach for the task assignment problem in homogeneous linear array networks. The task assignment problem for a homogeneous linear array network of n processors is first transformed into (n-1) two-terminal network flow problems, and then solved in time no worse than O(nm3) by applying the Goldberg-Tarjan's network flow algorithm for each two-terminal network flow problem.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.9 pp.2642-2648
- Publication Date
- 1991/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Algorithms, Data Structures and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Bog-Lae JO, Cheol-Hoon LEE, Dongmyun LEE, Myunghwan KIM, "Task Assignment in Homogeneous Linear Array Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E74-A, no. 9, pp. 2642-2648, September 1991, doi: .
Abstract: This letter deals with the problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. Recently, an optimal algorithm with the time complexity of O(n2m3 log n) has been suggested for the problem of assigning m interacting tasks to a linear array of n processors. They solved the problem by using the two-terminal network flow approach. In this letter, we propose a multiterminal network flow approach for the task assignment problem in homogeneous linear array networks. The task assignment problem for a homogeneous linear array network of n processors is first transformed into (n-1) two-terminal network flow problems, and then solved in time no worse than O(nm3) by applying the Goldberg-Tarjan's network flow algorithm for each two-terminal network flow problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_9_2642/_p
Copy
@ARTICLE{e74-a_9_2642,
author={Bog-Lae JO, Cheol-Hoon LEE, Dongmyun LEE, Myunghwan KIM, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Task Assignment in Homogeneous Linear Array Networks},
year={1991},
volume={E74-A},
number={9},
pages={2642-2648},
abstract={This letter deals with the problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. Recently, an optimal algorithm with the time complexity of O(n2m3 log n) has been suggested for the problem of assigning m interacting tasks to a linear array of n processors. They solved the problem by using the two-terminal network flow approach. In this letter, we propose a multiterminal network flow approach for the task assignment problem in homogeneous linear array networks. The task assignment problem for a homogeneous linear array network of n processors is first transformed into (n-1) two-terminal network flow problems, and then solved in time no worse than O(nm3) by applying the Goldberg-Tarjan's network flow algorithm for each two-terminal network flow problem.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Task Assignment in Homogeneous Linear Array Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2642
EP - 2648
AU - Bog-Lae JO
AU - Cheol-Hoon LEE
AU - Dongmyun LEE
AU - Myunghwan KIM
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1991
AB - This letter deals with the problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. Recently, an optimal algorithm with the time complexity of O(n2m3 log n) has been suggested for the problem of assigning m interacting tasks to a linear array of n processors. They solved the problem by using the two-terminal network flow approach. In this letter, we propose a multiterminal network flow approach for the task assignment problem in homogeneous linear array networks. The task assignment problem for a homogeneous linear array network of n processors is first transformed into (n-1) two-terminal network flow problems, and then solved in time no worse than O(nm3) by applying the Goldberg-Tarjan's network flow algorithm for each two-terminal network flow problem.
ER -
English
