252 citations · 435 across the 19 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011★ 3 cited
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami +2
The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significan…
cs.CC2011★ 1 cited
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…