Abstract
Given m matroids M_1,\ldots, M_m on the common ground set V, it is shown
that all maximal subsets of V, independent in the m matroids, can be
generated in quasi-polynomial time. More generally, given a system of
polymatroid inequalities f_1(X) ≥ t_1,\ldots,f_m(X) ≥ t_m with
quasi-polynomially bounded right hand sides t_1,\ldots,t_m, all minimal
feasible solutions X \subseteq V to the system can be generated in
incremental quasi-polynomial time. Our proof of these results is based on a
combinatorial inequality for polymatroid functions which may be of independent
interest. Precisely, for a polymatroid function f and an integer threshold
t≥q 1, let α=α(f,t) denote the number of maximal sets X
\subseteq V satisfying f(X)< t, let β=β(f,t) be the number of
minimal sets X \subseteq V for which f(X) ≥ t, and let n=|V|. We show
that α ≤\maxn,β^{(\log t)/c}}, where c=c(n,β) is the
unique positive root of the equation 2^c(n^{c/\logβ}-1)=1. In
particular, our bound implies that α ≤ (nβ)^{\log t}. We also
give examples of polymatroid functions with arbitrarily large t, n, α
and β for which α ≥ β^{(.551 \log t)/c.
