Geodesic
Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 4, pp. 154-161

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

The article states and proves pseudopolynomial complexity approximation algorithm for solving the scheduling theory known as $NP$-complete problem, namely minimizing maximum lateness on a single machine, interruption in job processing being banned. The bound value absolute error of criterion function for schedule constructed by algorithm is received.
Keywords: schedule, lateness, $NP$-complete, complexity.
Mots-clés : pseudopolynomial algorithm 
@article{UZKU_2008_150_4_a13,
     author = {O. N. Shulgina and N. K. Sherbakova},
     title = {Pseudopolynomial {Approximation} {Algorithm} for {Solving} the $NP${-Complete} {Problem} of {Minimizing} {Maximum} {Lateness}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {154--161},
     publisher = {mathdoc},
     volume = {150},
     number = {4},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/}
}
TY  - JOUR
AU  - O. N. Shulgina
AU  - N. K. Sherbakova
TI  - Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2008
SP  - 154
EP  - 161
VL  - 150
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/
LA  - ru
ID  - UZKU_2008_150_4_a13
ER  - 
%0 Journal Article
%A O. N. Shulgina
%A N. K. Sherbakova
%T Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2008
%P 154-161
%V 150
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/
%G ru
%F UZKU_2008_150_4_a13
O. N. Shulgina; N. K. Sherbakova. Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 4, pp. 154-161. http://geodesic.mathdoc.fr/item/UZKU_2008_150_4_a13/