Towards a strongly polynomial algorithm for strictly convex quadratic programs. An extension of Tardos' algorithm

Frieda Granot; Jadranka Skorin-Kapov

Towards a strongly polynomial algorithm for strictly convex quadratic programs. An extension of Tardos' algorithm

Frieda Granot
, Jadranka Skorin-Kapov

Dean's Office, College of Business

University of British Columbia

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

In a recent paper E. 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.

Original language	English
Pages (from-to)	225-236
Number of pages	12
Journal	Mathematical Programming, Series A
Volume	46
Issue number	2
State	Published - Feb 1990

Cite this

@article{f3877d64800744769b6b1b66dd3ef9a5,

title = "Towards a strongly polynomial algorithm for strictly convex quadratic programs. An extension of Tardos' algorithm",

abstract = "In a recent paper E. 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.",

author = "Frieda Granot and Jadranka Skorin-Kapov",

year = "1990",

month = feb,

language = "English",

volume = "46",

pages = "225--236",

journal = "Mathematical Programming, Series A",

number = "2",

}

TY - JOUR

T1 - Towards a strongly polynomial algorithm for strictly convex quadratic programs. An extension of Tardos' algorithm

AU - Granot, Frieda

AU - Skorin-Kapov, Jadranka

PY - 1990/2

Y1 - 1990/2

N2 - In a recent paper E. 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.

AB - In a recent paper E. 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.

UR - https://www.scopus.com/pages/publications/0025385329

M3 - Article

AN - SCOPUS:0025385329

VL - 46

SP - 225

EP - 236

JO - Mathematical Programming, Series A

JF - Mathematical Programming, Series A

IS - 2

ER -

Towards a strongly polynomial algorithm for strictly convex quadratic programs. An extension of Tardos' algorithm

Abstract

Other files and links

Fingerprint

Cite this