## DIMACS TR: 2001-14

## 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

DIMACS Home Page