QUADRATIC-PROGRAMMING IS IN NP

被引：75

作者：

VAVASIS, SA

机构：

[1] Department of Computer Science, Cornell University, Ithaca

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 36卷 / 02期

关键词：

Analysis of algorithms; computational complexity; quadratic programming;

D O I：

10.1016/0020-0190(90)90100-C

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Quadratic programming is an important example of optimization with applications to engineering design, combinatorial optimization, game theory, and economics. Garey and Johnson state that quadratic programming is NP-hard. In this paper we show that it lies in NP, thereby proving that it is NP-complete. © 1990.

引用

页码：73 / 77

页数：5