Detecting high log-densities
Aditya Bhaskara, Moses Charikar, Eden Chlamtáč, Uriel Feige, Aravindan Vijayaraghavan · 2010
In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n1/3 - c for some fixed c>0 (later estimated at around c= 1/90).