Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Aditya BhaskaraMoses CharikarVenkatesan GuruswamiAravindan VijayaraghavanYuan ZhouPublished in: CoRR (2011)
Keyphrases
- graph mining
- semidefinite
- similarity graph
- linear programming
- dense subgraphs
- np hard
- semidefinite programming
- lower bound
- linear programming relaxation
- convex relaxation
- linear systems
- mixed integer
- graph data
- social networks
- label propagation
- dynamic programming
- community discovery
- semi definite programming
- low degree
- image segmentation