A semi on-line algorithm for the partition problem
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 378855689 | ||
| 003 | CHVBK | ||
| 005 | 20180305123334.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 161128e20031201xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1515/156939203322733327 |2 doi |
| 035 | |a (NATIONALLICENCE)gruyter-10.1515/156939203322733327 | ||
| 245 | 0 | 2 | |a A semi on-line algorithm for the partition problem |h [Elektronische Daten] |c [E. Girlich, M. M. Kovalev, V. M. Kotov] |
| 520 | 3 | |a 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 and must be treated on-line there is no algorithm possessing the guaranteed estimate which is less than 1 + 1/√2 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. | |
| 540 | |a Copyright 2003, Walter de Gruyter | ||
| 700 | 1 | |a Girlich |D E. |4 aut | |
| 700 | 1 | |a Kovalev |D M. M. |4 aut | |
| 700 | 1 | |a Kotov |D V. M. |4 aut | |
| 773 | 0 | |t Discrete Mathematics and Applications |d Walter de Gruyter |g 13/6(2003-12-01), 619-625 |x 0924-9265 |q 13:6<619 |1 2003 |2 13 |o dma | |
| 856 | 4 | 0 | |u https://doi.org/10.1515/156939203322733327 |q text/html |z Onlinezugriff via DOI |
| 908 | |D 1 |a research article |2 jats | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1515/156939203322733327 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Girlich |D E. |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Kovalev |D M. M. |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Kotov |D V. M. |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Discrete Mathematics and Applications |d Walter de Gruyter |g 13/6(2003-12-01), 619-625 |x 0924-9265 |q 13:6<619 |1 2003 |2 13 |o dma | ||
| 900 | 7 | |b CC0 |u http://creativecommons.org/publicdomain/zero/1.0 |2 nationallicence | |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-gruyter | ||