hide
Free keywords:
-
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≥q 1, let α=α(f,t) denote the number
of maximal sets X \subseteq V satisfying f(X) < t, let β=β(f,t)
be the number of minimal sets X \subseteq V for which f(X) ≥ t,
and let n=|V|. We show that if β ≥ 2 then α ≤
β^(\log t)/c}, where c=c(n,β) is the unique positive root of the
equation 1=2^c(n^{c/\logβ}-1).
In particular, our bound implies that α ≤ (nβ)^{\log t} for all
β ≥ 1. We also give examples of polymatroid functions with arbitrarily
large t, n, α and β for which α ≥ β^{(.551 \log
t)/c}.
More generally, given a polymatroid function f:2^V \mapsto \ZZ
and an integral threshold t ≥ 1, consider an arbitrary
hypergraph \cH such that |\cH| ≥ 2 and f(H) ≥ 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| ≤q
|\cH|^{(\log t)/c(n,|\cH|). As an application, we show that
given a system of polymatroid inequalities f_1(X) ≥
t_1,\ldots,f_m(X) ≥ 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.
