Greedily Finding a Dense Subgraph |
| |
Authors: | Yuichi Asahiro Kazuo Iwama Hisao Tamaki Takeshi Tokuyama |
| |
Institution: | Department of Computer Science & Communication Engineering, Kyushu University, Fukuoka, 812, Japanf1;School of Informatics, Kyoto University, Kyoto, 606-01, Japan, f2;Department of Computer Science, Meiji University, Kawasaki, 214-71, Japan, f3;IBM Tokyo Research Laboratory, Yamato, 242, Japan, f4 |
| |
Abstract: | 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 ± O(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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|