Greedily finding a dense subgraph

Given an n-vertex graph with nonnegative edge weights and a positive intege r k less than or equal to n, our goal is to find a k-vertex subgraph with t he maximum weight. We study the following greedy algorithm for this problem : repeatedly remove a vertex with the minimum weighted-degree in the curren tly remaining graph, until exactly k vertices are left. We derive tight bou nds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)(2) - O(n(-1/3)) less than or equal to R less than or equal to (1/2 + n/2k)(2) + O(1/n) for k in the range n/3 less than or equal to k less tha n or equal to n and 2(n/k - 1)- O(1/k) less than or equal to R less than or equal to 2(n/k - 1) + O(n/k(2)) for k < n/3. For k = n/2, for example, the se bounds are 9/4 +/- O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with cur rently the best land much more complicated) approximation algorithm based o n semidefinite programming. (C) 2000 Academic Press.