English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

An Inequality for Polymatroid Functions and its Applications

MPS-Authors
/persons/resource/persons44374

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

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

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