On Quadratic Programming with a Ratio Objective

Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran +1

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 optim…