Local minima for indefinite quadratic knapsack problems (Q1186274)

The paper deals with the following problem: minimize \(x^ T Dx+d^ T x\) subject to \(\ell_ i\leq x_ i\leq u_ i\;(i=1,\dots,n)\), \(a^ T x=g\), where \(x\in R^ n\), \(D\) is a diagonal matrix, \(d\) and \(a\) are \(n\)- vectors, \(\ell_ 1,\dots,\ell_ n\), \(u_ 1,\dots,u_ n\) and \(g\) are real numbers. The author presents an extension of the MV algorithm to the indefinite case in which there is no restrictions on the signs of the diagonal entries of \(D\). This algorithm computes a local minimum in \(O(n(\log n)^ 2)\) steps.