The RPR2 rounding technique for semidefinite programs

Uriel Feige; M Langberg

doi:10.1016/j.jalgor.2004.11.003

Back

The RPR2 rounding technique for semidefinite programs

Journal article

Peer reviewed

The RPR2 rounding technique for semidefinite programs

Uriel Feige and M Langberg

Journal of Algorithms, Vol.60(1), pp.1-23

Jul/2006

DOI: https://doi.org/10.1016/j.jalgor.2004.11.003

Files and links (2)

url

https://doi.org/10.1016/j.jalgor.2004.11.003View

Published (Version of record) Restricted

url

https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1016/j.jalgor.2004.11.003View

Published (Version of record) Restricted

Abstract

Several combinatorial optimization problems can be approximated using algorithms based on semidefinite programming. In many of these algorithms a semidefinite relaxation of the underlying problem is solved yielding an optimal vector configuration v(1),..., v(n). This vector configuration is then rounded into a {0, 1} solution. We present a procedure called RPR2 (Random Projection followed by Randomized Rounding) for rounding the solution of such semidefinite programs. We show that the random hyperplane rounding technique introduced by Goemans and Williamson, and its variant that involves outward rotation, are both special cases of RPR2. We illustrate the use of RPR2 by presenting two applications. For Max-Bisection we improve the approximation ratio. For Max-Cut, we improve the tradeoff curve (presented by Zwick) that relates the approximation ratio to the size of the maximum cut in a graph. (c) 2004 Elsevier Inc. All rights reserved.

Details

Title: The RPR2 rounding technique for semidefinite programs
Creators: Uriel Feige (null) - 972WIS_INST___83
M Langberg (null)
Resource Type: Journal article
Publication Details: Journal of Algorithms, Vol.60(1), pp.1-23; Jul/2006
Number of pages: 23
Language: English
DOI: https://doi.org/10.1016/j.jalgor.2004.11.003
Record Identifier: 993266182103596

Metrics

21 Record Views