## Abstract

Let f: 2^{N} → Z^{+} be a polymatroid (an integer-valued non-decreasing submodular set function with f (Ø) = 0). We call S ⊆ N a base if f (S) = f (N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k: Σ_{i∈N}f_{A}(i) ≥ kf_{A}(N), ∀A ⊆ N} where f_{A}(S) = f (A ∪ S) - f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1-0(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 - 0(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 - ∈)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* ≤ (1 + 0(1))k*/lnf(N). Moreover it is known that unless NP ⊆ DTIME(n^{loglogn}), for any ∈ > 0, there is no polynomial time algorithm to obtain a (1 + ∈)/lnf(N)-approximation to m*. Our result generalizes and unifies two results in the literature.

Original language | English (US) |
---|---|

Pages (from-to) | 418-430 |

Number of pages | 13 |

Journal | Random Structures and Algorithms |

Volume | 35 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2009 |

## Keywords

- Integer packing
- Polymatroid
- Randomized algorithm

## ASJC Scopus subject areas

- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics