Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt





An Inequality for Polymatroid Functions and its Applications


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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

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

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.