TY - JOUR

T1 - Greedily Finding a Dense Subgraph

AU - Asahiro, Yuichi

AU - Iwama, Kazuo

AU - Tamaki, Hisao

AU - Tokuyama, Takeshi

N1 - Funding Information:
1Research supported in part by Science Research Grant 07458061, Ministry of Education, Japan. 2 Main part of the work done while author was at IBM Tokyo Research Laboratory.

PY - 2000/2

Y1 - 2000/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0042657622&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042657622&partnerID=8YFLogxK

U2 - 10.1006/jagm.1999.1062

DO - 10.1006/jagm.1999.1062

M3 - Article

AN - SCOPUS:0042657622

SN - 0196-6774

VL - 34

SP - 203

EP - 221

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -