Harmonic algorithm for 3-dimensional strip packing problem
Nikhil Bansal, Xin Han, et al.
SODA 2007
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.
Nikhil Bansal, Xin Han, et al.
SODA 2007
Christos H. Papadimitriou, Prabhakar Raghavan, et al.
FOCS 1994
Andris Ambainis, Kazuo Iwama, et al.
Computational Complexity
Nader H. Bshouty, Sally A. Goldman, et al.
STOC 1996