An inequality for polymatroid functions and its applications. (Q1410680)

A polymatroid function \(f : 2^V \rightarrow Z\), where \(V\) is a finite set, is a function with \(f(\emptyset) = 0\) which is submodular and nondecreasing. Given such a function and an integer \(t \geq 1\), setting \(n = | V| \), and letting \(\alpha\) denote the number of maximal sets \(X \subseteq V\) such that \(f(X) < t\) and \(\beta\) the number of minimal sets \(X \subseteq V\) such that \(f(X) \geq t\), the present paper proves an inequality implying the quasi-polynomial bound \(\alpha \leq (n \beta)^{\log t}\) whenever \(\beta \geq 1\). The paper discusses the extent to which the inequality is tight, as well as some related inequalities. Several applications are given, fitting under the following broad umbrella: Given a system \(f_i(X) \geq t_i\) for \(1 \leq i \leq m\), where the \(f_i\) are polymatroid functions, it is shown that all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. Among the special cases is the following variant of the matroid intersection problem: Given \(m\) matroids on the set \(V\), enumerate the maximal sets \(X \subseteq V\) such that \(X\) is independent in each of the matroids.