The search functionality is under construction.

The search functionality is under construction.

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=1}^{k} 1/*i* is the *k*th 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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Toshihiro FUJITO, "Approximating Polymatroid Packing and Covering" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1066-1070, May 2002, doi: .

Abstract: 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=1}^{k} 1/*i* is the *k*th 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1066/_p

Copy

@ARTICLE{e85-a_5_1066,

author={Toshihiro FUJITO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Approximating Polymatroid Packing and Covering},

year={2002},

volume={E85-A},

number={5},

pages={1066-1070},

abstract={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=1}^{k} 1/*i* is the *k*th 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.},

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - Approximating Polymatroid Packing and Covering

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1066

EP - 1070

AU - Toshihiro FUJITO

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2002

AB - 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=1}^{k} 1/*i* is the *k*th 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.

ER -