Back to Search
Start Over
A semi on-line algorithm for the partition problem.
- Source :
- Discrete Mathematics & Applications; 2003, Vol. 13 Issue 6, p619-625, 7p
- Publication Year :
- 2003
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
PARTITIONS (Mathematics)
NUMBER theory
ALGEBRA
MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 09249265
- Volume :
- 13
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- Discrete Mathematics & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 12146741
- Full Text :
- https://doi.org/10.1515/156939203322733327