

(LaTeX) 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 quasipolynomial time. More generally, given a system of polymatroid inequalities $f_1(X) \ge t_1,\ldots,f_m(X) \ge t_m$ with quasipolynomially bounded right hand sides $t_1,\ldots,t_m$, all minimal feasible solutions $X \subseteq V$ to the system can be generated in incremental quasipolynomial 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\geq 1$, let $\alpha=\alpha(f,t)$ denote the number of maximal sets $X \subseteq V$ satisfying $f(X)< t$, let $\beta=\beta(f,t)$ be the number of minimal sets $X \subseteq V $ for which $f(X) \ge t$, and let $n=V$. We show that $\alpha \le\max\{n,\beta^{(\log t)/c}\}$, where $c=c(n,\beta)$ is the unique positive root of the equation $2^c(n^{c/\log\beta}1)=1$. In particular, our bound implies that $\alpha \le (n\beta)^{\log t}$. We also give examples of polymatroid functions with arbitrarily large $t, n, \alpha$ and $\beta$ for which $\alpha \ge \beta^{(.551 \log t)/c}$. 




Download
Access Level: 
Public 
