The dense k-subgraph problem
This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O (n(delta)), for some delta < 1/3.
approximation algorithms dense subgraph