Disjoint bases in a polymatroid

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∈Nf_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.