Note: 

(LaTeX) Abstract: 
An integralvalued set function $f:2^V \mapsto \ZZ$ is called
polymatroid if it is submodular, nondecreasing, 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 quasipolynomially bounded right
hand sides $t_1,\ldots,t_m$, all minimal feasible solutions to
this system can be generated in incremental quasipolynomial time. In contrast to this result, the generation of all maximal
infeasible sets is an NPhard problem for many polymatroid
inequalities of small range. 
URL for the Abstract: 

Categories,
Keywords: 
dualization, incremental algorithm, independent set, matroid, submodular function, polymatroid function, system of polymatroid inequalities, transversal hypergraph 
HyperLinks / References / URLs: 

Copyright Message: 

Personal Comments: 

Download
Access Level: 
Intranet 
