Disjoint bases in a polymatroid

Gruia Cǎlinescu, Chandra Chekuri, Jan Vondrák

Research output: Contribution to journalArticlepeer-review

Abstract

Let f: 2N → 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∈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-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(nloglogn), 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 languageEnglish (US)
Pages (from-to)418-430
Number of pages13
JournalRandom Structures and Algorithms
Volume35
Issue number4
DOIs
StatePublished - Dec 2009

Keywords

  • Integer packing
  • Polymatroid
  • Randomized algorithm

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Disjoint bases in a polymatroid'. Together they form a unique fingerprint.

Cite this