On quadratic programming with a ratio objective

Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form ∑i≠j aij x i xj. 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 (Formula Presented) 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 Õ(n1/3) approximation algorithm for QP-ratio. We also give a 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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages109-120
Number of pages12
EditionPART 1
DOIs
StatePublished - Dec 1 2012
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: Jul 9 2012Jul 13 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
CountryUnited Kingdom
CityWarwick
Period7/9/127/13/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On quadratic programming with a ratio objective'. Together they form a unique fingerprint.

  • Cite this

    Bhaskara, A., Charikar, M., Manokaran, R., & Vijayaraghavan, A. (2012). On quadratic programming with a ratio objective. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings (PART 1 ed., pp. 109-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7391 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-31594-7_10