Pregledni rad
On strongly polynomial algorithms for some classes of quadratic programming problems
J. Skorin-Kapov
Sažetak
In this paper we survey some results concerning polynomial and/or
strongly polynomial solvability of some classes of quadratic programming problems.
The discussion on polynomial solvability of continuous convex quadratic programming is followed by a couple of models for
quadratic integer programming which, due to their special structure, allow polynomial (or even strongly polynomial) solvability. The theoretical merit of those results stems from the fact that a
running time (i.e. the number of elementary arithmetic operations) of a strongly polynomial algorithm is independent of the input size of the problem.
Ključne riječi
quadratic programming; polynomial algorithms; strongly polynomial algorithms; job scheduling problems
Hrčak ID:
1800
URI
Datum izdavanja:
20.12.1997.
Posjeta: 1.916 *