Disjoint bases in a polymatroid

Let f : 2 N → $\cal {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 − o (1)) k */ln f ( N ) and give a randomized polynomial time algorithm to find (1 − o (1)) k */ln f ( 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 */ln f ( N ) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m * < (1 + o (1)) k */ln f ( N ). Moreover it is known that unless NP ⊆ DTIME ( n log log n ), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/ln f ( N )‐approximation to m *. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009