User Manual Privacy Policy Disclaimer Contact us
  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: http://hdl.handle.net/11858/00-001M-0000-0019-ED6F-6
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.