2004/12/23 by Moses Charikar, Anthony Wirth · 9 citations
Computer Science · Mathematics · Engineering · #Complexity and Algorithms in Graphs #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques
paper · doi:10.1109/focs.2004.39
openalex publication_date 2004/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ -1, 1/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.