Name
Abstract | ||
|---|---|---|
In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-form formula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an $[m^2(1-\cos\frac{2\pi}{m})/8\pi]$-approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of $\pi/4 \approx 0.7854$, which is better than the ratio of $2/\pi \approx 0.6366$ for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1137/04061341X | SIAM Journal on Optimization |
Keywords | Field | DocType |
approximation ratio,hermitian quadratic functions,complex sdp relaxation.,max-3-cut model,approximation algorithm,worst-case performance ratio,semidefinite programming,complex semidefinite programming relaxation,closed-form formula,positive semidefinite hermitian form,hermitian complex form,performance ratio,randomized algorithms,discrete quadratic optimization problem,positive semidefinite,complex quadratic optimization,quadratic optimization | Discrete mathematics,Approximation algorithm,Mathematical optimization,Combinatorics,Quadratically constrained quadratic program,Positive-definite matrix,Multivariate random variable,Quadratic programming,Hermitian matrix,Semidefinite embedding,Semidefinite programming,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 3 | 1052-6234 |
Citations | PageRank | References |
63 | 5.01 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shuzhong Zhang | 1 | 2808 | 181.66 |
| Yongwei Huang | 2 | 814 | 50.83 |