On Quadratic Programming with a Ratio Objective

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form \sum_{i \ne j} a_{ij} x_i x_j. 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{\sum_{i \not = j} a_{ij} x_i x_j}{\sum x_i^2}, and Normalized QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j} a_{ij} x_i x_j}{\sum d_i x_i^2}, where d_i = \sum_j |a_{ij}| We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an $\tilde{O}(n^{1/3})$ algorithm for QP-ratio. We also obtain an $\tilde{O}(n^{1/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^\epsilon approximation (for \epsilon roughly 1/10) seems out of reach of current techniques.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On Quadratic Programming with a Ratio Objective does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Quadratic Programming with a Ratio Objective, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Quadratic Programming with a Ratio Objective will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-455516

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.