approximation algorithms – Page 8

Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation

Published: 2003/01/19

Approximation Algorithms approximation algorithms, performance ratio, quadratic maximization, semidefinite relaxation

In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. … Read more

Further Results on Approximating Nonconvex Quadratic Optimizationby Semidefinite Programming Relaxation

Published: 2001/12/17

Paul Tseng

Quadratic Programming, Semi-definite Programming approximation algorithms, quadratically constrained quadratic optimization, semidefinite relaxation

We study approximation bounds for the SDP relaxation of quadratically constrained quadratic optimization: min f^0(x) subject to f^k(x)

Solving standard quadratic optimization problems via linear, semidefinite and copositive programming

Published: 2001/05/23, Updated: 2007/05/14

Combinatorial Optimization, Global Optimization Theory, Semi-definite Programming approximation algorithms, copositive programming, semidefinite programming, stability number, standard quadratic optimization

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities … Read more