Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Journal Article

An Inequality for Polymatroid Functions and its Applications


Elbassioni,  Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Boros, E., Elbassioni, K. M., Khachiyan, L., & Gurvich, V. (2003). An Inequality for Polymatroid Functions and its Applications. Discrete applied mathematics, 131, 27.

Cite as:
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.