Motion planning on a graph (extended abstract)
Christos H. Papadimitriou, Prabhakar Raghavan, et al.
FOCS 1994
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.
Christos H. Papadimitriou, Prabhakar Raghavan, et al.
FOCS 1994
Magnús M. Halldórsson, Kazuo Iwama, et al.
ACM Transactions on Algorithms
Andris Ambainis, Kazuo Iwama, et al.
Computational Complexity
Hisao Tamaki
Journal of Computer and System Sciences