An inequality for polymatroid functions and its applications

Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan

ABSTRACT

An integral-valued set function $f:2^V \mapsto \ZZ$ is called polymatroid if it is submodular, non-decreasing, and $f(\emptyset)=0$. Given 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 if $\beta \ge 2$ then $\alpha \le \beta^{(\log t)/c}$, where $c=c(n,\beta)$ is the unique positive root of the equation $1=2^c(n^{c/\log\beta}-1)$. In particular, our bound implies that $\alpha \le (n\beta)^{\log t}$ for all $\beta \ge 1$. We also give examples of polymatroid functions with arbitrarily large $t, n, \alpha$ and $\beta$ for which $\alpha \ge \beta^{(.551 \log t)/c}$.

More generally, given a polymatroid function $f:2^V \mapsto \ZZ$ and an integral threshold $t \ge 1$, consider an arbitrary hypergraph $\cH$ such that $|\cH| \ge 2$ and $f(H) \ge t$ for all $H \in \cH$. Let $\cS$ be the family of all maximal independent sets $X$ of $\cH$ for which $f(X) < t$. Then $|\cS| \leq |\cH|^{(\log t)/c(n,|\cH|)}$. As an application, we show that given a system of polymatroid inequalities $f_1(X) \ge t_1,\ldots,f_m(X) \ge t_m$ with quasi-polynomially bounded right hand sides $t_1,\ldots,t_m$, all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal infeasible sets is an NP-hard problem for many polymatroid inequalities of small range.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-14.ps.gz