Skip to main content

On Quadratic Programming with a Ratio Objective

Author(s): Bhaskara, Aditya; Charikar, Moses; Manokaran, Rajsekar; Vijayaraghavan, Aravindan

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1mr6r
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBhaskara, Aditya-
dc.contributor.authorCharikar, Moses-
dc.contributor.authorManokaran, Rajsekar-
dc.contributor.authorVijayaraghavan, Aravindan-
dc.date.accessioned2021-10-08T19:44:41Z-
dc.date.available2021-10-08T19:44:41Z-
dc.date.issued2012en_US
dc.identifier.citationBhaskara, Aditya, Moses Charikar, Rajsekar Manokaran, and Aravindan Vijayaraghavan. "On Quadratic Programming with a Ratio Objective." Automata, Languages, and Programming (2012): 109-120. doi: 10.1007/978-3-642-31594-7_10en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttps://arxiv.org/pdf/1101.1710.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1mr6r-
dc.description.abstractQuadratic Programming (QP) is the well-studied problem of maximizing over { − 1,1} values the quadratic form ∑  i ≠ j a ij x i x j . QP captures many known combinatorial optimization problems, and assuming the Unique Games conjecture, Semidefinite Programming (SDP) 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 problem we study is 𝖰𝖯-𝖱𝖺𝗍𝗂𝗈:\ \ max{−1,0,1}𝑛∑𝑖≠𝑗𝑎𝑖𝑗𝑥𝑖𝑥𝑗∑𝑥2𝑖 This is a natural relative of several well studied problems (in fact Trevisan introduced a normalized variant as a stepping stone towards a spectral algorithm for Max Cut Gain). Quadratic ratio problems are good testbeds for both algorithms and complexity because the techniques used for quadratic problems for the { − 1,1} and {0,1} domains do not seem to carry over to the { − 1,0,1} domain. We give approximation algorithms and evidence for the hardness of approximating these problems. We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an 𝑂̃ (𝑛1/3) approximation algorithm for QP-ratio. We also give a 𝑂̃ (𝑛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: one is based on the assumption that random instances of Max k-AND are hard to approximate, and the other makes a connection to a ratio version of Unique Games. 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.en_US
dc.format.extent109 - 120en_US
dc.language.isoen_USen_US
dc.relation.ispartofAutomata, Languages, and Programmingen_US
dc.relation.ispartofseriesLecture Notes in Computer Science;-
dc.rightsAuthor's manuscripten_US
dc.titleOn Quadratic Programming with a Ratio Objectiveen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-642-31594-7_10c-
dc.identifier.eissn1611-3349-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
OnQuadraticProgrammingRatioObjective.pdf340.57 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.