We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A semi on-line algorithm for the partition problem.
- Authors
Girlich, E.; Kovaley, M. M.; Kotov, V. M.
- Abstract
The distribution of jobs in a system with m identical parallel processors which minimises the load of the maximally loaded processor is an NP-hard problem. Many approximate algorithms are developed for this problem, but for the version of the problem where the jobs arrive ad must be treated on-line there is no algorithm possessing the guaranteed estimate which is less than 1 + 1 / ... for m ≥ 4 and tends to 1.837 as m → ∞. In this paper, we consider the version of the problem where jobs arrive one by one and must be treated on-line under the additional condition that the total duration of the jobs is known. For this version of the problem we suggest an algorithm with the guaranteed estimate equal to 5/3.
- Subjects
ALGORITHMS; PARTITIONS (Mathematics); NUMBER theory; ALGEBRA; MATHEMATICS
- Publication
Discrete Mathematics & Applications, 2003, Vol 13, Issue 6, p619
- ISSN
0924-9265
- Publication type
Article
- DOI
10.1515/156939203322733327