For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Approximating Polymatroid Packing and Covering
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
combinatorial problems, design of algorithms, optimization,
Full Text: PDF>>
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.