|
This article is cited in 10 scientific papers (total in 10 papers)
The discretization problem: analysis of computational complexity, and polynomially solvable subclasses
D. I. Kogan, Yu. S. Fedosenko
Abstract:
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.
Received: 01.07.1994
Citation:
D. I. Kogan, Yu. S. Fedosenko, “The discretization problem: analysis of computational complexity, and polynomially solvable subclasses”, Diskr. Mat., 8:3 (1996), 135–147; Discrete Math. Appl., 6:5 (1996), 435–447
Linking options:
https://www.mathnet.ru/eng/dm534https://doi.org/10.4213/dm534 https://www.mathnet.ru/eng/dm/v8/i3/p135
|
Statistics & downloads: |
Abstract page: | 800 | Full-text PDF : | 435 | First page: | 1 |
|