Disjoint bases in a polymatroid |
| |
Authors: | Gruia C?linescu Chandra Chekuri Jan Vondrák |
| |
Institution: | 1. Computer Science Department, Illinois Institute of Technology, Chicago, Illinois;2. Department of Computer Science, University of Illinois, Urbana, Illinois 61801;3. Department of Mathematics, Princeton University, Princeton, New Jersey 08544 |
| |
Abstract: | Let f : 2N → + 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εNfA(i) ≥ kfA(N),?A ? N} where fA(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*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(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 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(nlog log n), 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. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 |
| |
Keywords: | polymatroid integer packing randomized algorithm |
|
|