The polynomial solvability of convex quadratic programming

By M. Kozlov, S. Tarasov, L. Khachiyan. 1980

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Causal Modeling-Based Discrimination Discovery and Removal: Criteria, Bounds, and Algorithms (2019, background): “According to [36], the quadratic programming can be solved in polynomial time.”
The NP-Completeness Column: An Ongoing Guide (1982, unknown): “In particular, it has been used to solve the convex quadratic programming problem in polynomial time [ 42 ] as well as the linear complementarity problem for positive definite symmetric matrices [11] (The general LIN-EAR COMPLEMENTARITY problem, mentioned in the comments to this problem in [G&J], ha”
Safe receding horizon control for aggressive MAV flight with limited range sensing (2015, unknown): “From [10] the QP will take O(b3.”
General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming (2017, background): “ [Coo71, Kar72]. In particular, [Sah74] showed that QP with a negative deﬁnite quadratic term is NP-hard. On the other hand, QP with convex objective function was shown to be polynomial-time solvable [KTK80]. Quadratically constrained quadratic programming. Van de Panne [VdP66] studied a special cla”
Annual Conference Computational Learning Theory: Preface (2012, methodology): “This problem is polynomial time solvable by Quadratic Programing or by the Ellipsoid Method Kozlov et al. (1979).”