TOWARDS A STRONGLY POLYNOMIAL ALGORITHM FOR STRICTLY CONVEX QUADRATIC PROGRAMS - AN EXTENSION OF TARDO ALGORITHM

被引：8

作者：

GRANOT, F

SKORINKAPOV, J

机构：

[1] Faculty of Commerce and Business Administration, The University of British Columbia, Vancouver, V6T 1Y8, B.C.

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 46卷 / 02期

关键词：

Quadratic programming; strong polynomiality;

D O I：

10.1007/BF01585740

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In a recent paper Tardos described a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In this paper we extend Tardos' results and present a polynomial algorithm for solving strictly convex quadratic programming problems in which the number of arithmetic steps is independent of the size of the numbers in the right hand side and the linear cost coefficients. © 1990 North-Holland.

引用

页码：225 / 236

页数：12

共 13 条

[1]

[Anonymous], 1988, GEOMETRIC ALGORITHMS, DOI DOI 10.1007/978-3-642-97881-4

[2]

BACHEM A, 1978, Z ANGEW MATH METCH, V58, P459

[3]

COTTLE RW, 1963, Q APPL MATH, V21, P237

[4]

DEBIESSE JL, 1980, ANN TELECOMMUN, V35, P91

[5]

Dorn WS, 1960, Q APPL MATH, V18, P155, DOI [10.1090/qam/112751, DOI 10.1090/QAM/112751]

[6]

Eaves B. C., 1971, Management Science, V17, P698, DOI 10.1287/mnsc.17.11.698

[7] SYSTEMS OF DISTINCT REPRESENTATIVES AND LINEAR ALGEBRA [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICAL SCIENCES, 1967, B 71 (04) :241-+

[8]

Held M., 1974, Mathematical Programming, V6, P62, DOI 10.1007/BF01580223

[9] A POLYNOMIALLY BOUNDED ALGORITHM FOR A SINGLY CONSTRAINED QUADRATIC PROGRAM [J].

HELGASON, R ;

KENNINGTON, J ;

LALL, H .

MATHEMATICAL PROGRAMMING, 1980, 18 (03) :338-343

[10] EFFECTIVE SUBGRADIENT PROCEDURE FOR MINIMAL COST MULTICOMMODITY FLOW PROBLEMS [J].

KENNINGTON, J ;

SHALABY, M .

MANAGEMENT SCIENCE, 1977, 23 (09) :994-1004

← 1 2 →