Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Boros, Endre Elbassioni, Khaled M. Khachiyan, Leonid Gurvich, Vladimir dblp dblp dblp dblp Not MPG Author(s): Boros, Endre Gurvich, Vladimir Khachiyan, Leonid
 BibTeX cite key*: Elbassioni2003a

 Title
 Title*: An Inequality for Polymatroid Functions and its Applications

 Journal
 Journal Title*: Discrete Applied mathematics Journal's URL: Download URL for the article: Language: English

 Publisher
 Publisher's Name: Elsevier Publisher's URL: Publisher's Address: ISSN:

 Vol, No, pp, Date
 Volume*: 131 Number: Publishing Date: 2003 Pages*: 27 Number of VG Pages: Page Start: 255 Page End: 281 Sequence Number: DOI:

 Note: (LaTeX) 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\geq 1$, let $\alpha=\alpha(f,t)$ denote the number of maximal sets $X \subseteq V$ satisfying $f(X) < t$, let $\beta=\beta(f,t)$ be the number of minimal sets $X \subseteq V$ for which $f(X) \ge t$, and let $n=|V|$. We show that if $\beta \ge 2$ then $\alpha \le \beta^{(\log t)/c}$, where $c=c(n,\beta)$ is the unique positive root of the equation $1=2^c(n^{c/\log\beta}-1)$. In particular, our bound implies that $\alpha \le (n\beta)^{\log t}$ for all $\beta \ge 1$. We also give examples of polymatroid functions with arbitrarily large $t, n, \alpha$ and $\beta$ for which $\alpha \ge \beta^{(.551 \log t)/c}$. More generally, given a polymatroid function $f:2^V \mapsto \ZZ$ and an integral threshold $t \ge 1$, consider an arbitrary hypergraph $\cH$ such that $|\cH| \ge 2$ and $f(H) \ge t$ for all $H \in \cH$. Let $\cS$ be the family of all maximal independent sets $X$ of $\cH$ for which \$f(X)

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Elbassioni2003a,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {An Inequality for Polymatroid Functions and its Applications},
JOURNAL = {Discrete Applied mathematics},
PUBLISHER = {Elsevier},
YEAR = {2003},
VOLUME = {131},
PAGES = {27},
}

Entry last modified by Christine Kiesel, 07/15/2014
Edit History (please click the blue arrow to see the details)

 Editor(s) [Library] Created 02/22/2005 06:41:34 PM Revisions 2. 1. 0. Editor(s) Christine Kiesel Khaled Elbassioni Khaled Elbassioni Edit Dates 02.05.2007 15:40:17 04/20/2006 06:41:29 PM 02/22/2005 06:41:34 PM