The search functionality is under construction.
The search functionality is under construction.

Approximating Polymatroid Packing and Covering

Toshihiro FUJITO

  • Full Text Views

    0

  • Cite this

Summary :

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)=Σi=1k 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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1066-1070
Publication Date
2002/05/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword