Approximating Polymatroid Packing and Covering(Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k) = Σ^k_<i=1> 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k + 1) for packing and H(k) - 1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.
社団法人電子情報通信学会の論文
2002-05-01