Skip to the main content

Review article

On strongly polynomial algorithms for some classes of quadratic programming problems

J. Skorin-Kapov


Full text: english pdf 157 Kb

page 95-105

downloads: 1.463

cite


Abstract

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.

Keywords

quadratic programming; polynomial algorithms; strongly polynomial algorithms; job scheduling problems

Hrčak ID:

1800

URI

https://hrcak.srce.hr/1800

Publication date:

20.12.1997.

Visits: 1.916 *