Article: A successive linear programming algorithm for SDP relaxation of binary quadratic programming (1).(Technical report)

Abstract In this paper, we obtain a successive linear programming algorithm for solving the semidefinite programming (SDP) relaxation of the binary quadratic programming. Combining with a randomized method of Goemans and Williamson, it provides an efficient approximation for the binary quadratic programming. Furthermore, its convergence result is given. At last, We report some numerical examples to compare our method with the interior-point method on Maxcut problem.

Keywords Binary quadratic programming, successive quadratic programming algorithm, semidefinite programming, randomized method.

[section] 1. Introduction

In this paper, we consider ...

Related newspaper, magazine, and journal articles:

 
 
Newsweek Harper's Magazine The Washington Post Chicago Tribune Crain's Chicago Business PRNewswire Pediatric News The Nation Advertising Age The Economist (US) A FREE trial gives you access to over 80 million articles! Access over 6,500 publications with a FREE trial!