On quadratic programming with a ratio objective

DOI10.1007/978-3-642-31594-7_10MaRDI QIDQ2843240zbMATH OpenOpenAlexFDO

Authors Aditya Bhaskara, Rajsekar Manokaran, Moses Charikar, Aravindan Vijayaraghavan

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.1710

zbMATH Keywords

approximation algorithmscombinatorial optimizationquadratic programmingratio objectivesemidefinite programmingunique games conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Quadratic programming (90C20) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Abstract: Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form sum_{i

e 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 ot = j} a_{ij} x_i x_j}{sum x_i^2}, and Normalized QP-Ratio : max_{{-1,0,1}^n} frac{sum_{i

ot = 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 $ildeO(n^{1/3})$ algorithm for QP-ratio. We also obtain an $ildeO(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.

Recommendations

• Complex Quadratic Optimization and Semidefinite Programming
• On approximating complex quadratic optimization problems via semidefinite programming relaxations
• On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations
• Approximating quadratic programming with bound and quadratic constraints
• Approximation algorithms for quadratic programming

Cited in

(4)

• Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games
• Approximating sparse quadratic programs
• Ratio dynamic programs
• Modified ratio objective approach in mathematical programming

This page was built for publication: On quadratic programming with a ratio objective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843240)