Title | ||
---|---|---|
An improved lower bound and approximation algorithm for binary constrained quadratic programming problem |
Abstract | ||
---|---|---|
This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem together with a worst case performance analysis for the algorithm is provided. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/s10898-009-9504-1 | J. Global Optimization |
Keywords | Field | DocType |
Quadratic integer programming,Lower bound,Approximation algorithm,Spectral decomposition | Second-order cone programming,Approximation algorithm,Binary quadratic form,Mathematical optimization,Quadratically constrained quadratic program,Upper and lower bounds,Quadratic function,Quadratic programming,Sequential quadratic programming,Mathematics | Journal |
Volume | Issue | ISSN |
48 | 3 | 0925-5001 |
Citations | PageRank | References |
3 | 0.45 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cheng Lu | 1 | 9 | 1.60 |
Zhenbo Wang | 2 | 59 | 9.43 |
Wenxun Xing | 3 | 96 | 10.67 |