Geodesic
The discretization problem: analysis of computational complexity, and polynomially solvable subclasses
Diskretnaya Matematika, Tome 8 (1996) no. 3, pp. 135-147.

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

We consider the problem to draw up the optimal schedule for a single server fed by a finite deterministic flow of claims, minimizing the sum of linear functions of individual penalties of claims. For the introduced hierarchies of subclasses of the mass problem under consideration we give the bounds where NP-complexity takes place. We demonstrate that if we pose some natural, from the practical viewpoint, constraints on the class of schedules or models, then we are able to construct polynomial algorithms to draw up optimal schedules, which are based on recursive dynamic programming relations.This work was supported by the Russian Foundation for Basic Research, grant 93–013–16253. 
@article{DM_1996_8_3_a10,
     author = {D. I. Kogan and Yu. S. Fedosenko},
     title = {The discretization problem: analysis of computational complexity, and polynomially solvable subclasses},
     journal = {Diskretnaya Matematika},
     pages = {135--147},
     publisher = {mathdoc},
     volume = {8},
     number = {3},
     year = {1996},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1996_8_3_a10/}
}
TY  - JOUR
AU  - D. I. Kogan
AU  - Yu. S. Fedosenko
TI  - The discretization problem: analysis of computational complexity, and polynomially solvable subclasses
JO  - Diskretnaya Matematika
PY  - 1996
SP  - 135
EP  - 147
VL  - 8
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1996_8_3_a10/
LA  - ru
ID  - DM_1996_8_3_a10
ER  - 
%0 Journal Article
%A D. I. Kogan
%A Yu. S. Fedosenko
%T The discretization problem: analysis of computational complexity, and polynomially solvable subclasses
%J Diskretnaya Matematika
%D 1996
%P 135-147
%V 8
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1996_8_3_a10/
%G ru
%F DM_1996_8_3_a10
D. I. Kogan; Yu. S. Fedosenko. The discretization problem: analysis of computational complexity, and polynomially solvable subclasses. Diskretnaya Matematika, Tome 8 (1996) no. 3, pp. 135-147. http://geodesic.mathdoc.fr/item/DM_1996_8_3_a10/