Premium
Disjoint bases in a polymatroid
Author(s) -
Călinescu Gruia,
Chekuri Chandra,
Vondrák Jan
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20274
Subject(s) - combinatorics , disjoint sets , upper and lower bounds , mathematics , base (topology) , matroid , function (biology) , integer (computer science) , submodular set function , time complexity , discrete mathematics , computer science , mathematical analysis , evolutionary biology , biology , programming language
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