Hisao Tamaki
Journal of Computer and System Sciences
Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)2 - O(n-1/3) ≤ R ≤ (1/2 + n/2k)2 + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k - 1) - O(1/k) ≤ R ≤ 2(n/k - 1) + O(n/k2) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± 0(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming. © 2000 Academic Press.
Hisao Tamaki
Journal of Computer and System Sciences
Hisao Tamaki
SIAM Journal on Computing
Anna R. Karlin, Greg Nelson, et al.
STOC 1994
Nader H. Bshouty, Sally A. Goldman, et al.
STOC 1996