Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm |
| |
| Authors: | Frieda Granot Jadranka Skorin-Kapov |
| |
| Institution: | (1) Faculty of Commerce and Business Administration, The University of British Columbia, V6T 1Y8 Vancouver, B.C., Canada;(2) Present address: W.A. Harriman School for Management and Policy, State University of New York at Stony Brook, Stony Brook, NY, USA |
| |
| Abstract: | 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.This research was partially supported by the Natural Sciences and Engineering Research Council of Canada Grant 5-83998. |
| |
| Keywords: | Quadratic programming strong polynomiality |
| 本文献已被 SpringerLink 等数据库收录！ |
