2011/01/10 by Aditya Bhaskara, Moses Charikar, Bhaskara, Aditya +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1101.1710
openalex publication_date 2011/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quadratic Programming (QP) is the well-studied problem of maximizing over -1,1 values the quadratic form ∑i ≠ j aij xi xj. QP captures many known combinatorial optimization problems, and assuming the unique games conjecture, semidefinite programming techniques give optimal approximation algorithms. We extend this body of work by initiating the study of Quadratic Programming problems where the variables take values in the domain -1,0,1. The specific problems we study are QP-Ratio : max_\-1,0,1\n \frac∑i \not = j aij xi xj∑ xi2, and Normalized QP-Ratio : max_\-1,0,1\n \frac∑i \not = j aij xi xj∑ di xi2, where di = ∑j |aij| We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an O(n1/3) algorithm for QP-ratio. We also obtain an O(n1/4) approximation for bipartite graphs, and better algorithms for special cases. As with other problems with ratio objectives (e.g. uniform sparsest cut), it seems difficult to obtain inapproximability results based on P!=NP. We give two results that indicate that QP-Ratio is hard to approximate to within any constant factor. We also give a natural distribution on instances of QP-Ratio for which an nεapproximation (for εroughly 1/10) seems out of reach of current techniques.