Geodesic
A~semi on-line algorithm for the partition problem
Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 133-140

Voir la notice de l'article provenant de la source Math-Net.Ru

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/\sqrt 2$ for $m\geq 4$ and tends to $1{.}837$ as $m\to\infty$. 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$. 
@article{DM_2003_15_4_a9,
     author = {E. Girlikh and M. M. Kovalev and V. M. Kotov},
     title = {A~semi on-line algorithm for the partition problem},
     journal = {Diskretnaya Matematika},
     pages = {133--140},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/}
}
TY  - JOUR
AU  - E. Girlikh
AU  - M. M. Kovalev
AU  - V. M. Kotov
TI  - A~semi on-line algorithm for the partition problem
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 133
EP  - 140
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/
LA  - ru
ID  - DM_2003_15_4_a9
ER  - 
%0 Journal Article
%A E. Girlikh
%A M. M. Kovalev
%A V. M. Kotov
%T A~semi on-line algorithm for the partition problem
%J Diskretnaya Matematika
%D 2003
%P 133-140
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/
%G ru
%F DM_2003_15_4_a9
E. Girlikh; M. M. Kovalev; V. M. Kotov. A~semi on-line algorithm for the partition problem. Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 133-140. http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/