Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 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
 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
 Editor(s): Not MPII Editor(s): Krzysztof Diks, Wojciech Rytter
 BibTeX cite key*: Elbassioni2002b

 Title, Booktitle
 Title*: Matroid Intersections, Polymatroid Inequalities, and Related Problems MFCS02.pdf (186.23 KB) Booktitle*: Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Warsaw, Poland Language: English Event Date* (no longer used): Organization: Event Start Date: 26 August 2002 Event End Date: 30 August 2002

 Publisher
 Name*: Springer URL: Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2420 Number: Month: August Pages: 143-154 Year*: 2002 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) Abstract: Given $m$ matroids $M_1,\ldots, M_m$ on the common ground set $V$, it is shown that all maximal subsets of $V$, independent in the $m$ matroids, can be generated in quasi-polynomial time. More generally, given a system of polymatroid inequalities $f_1(X) \ge t_1,\ldots,f_m(X) \ge t_m$ with quasi-polynomially bounded right hand sides $t_1,\ldots,t_m$, all minimal feasible solutions $X \subseteq V$ to the system can be generated in incremental quasi-polynomial time. Our proof of these results is based on a combinatorial inequality for polymatroid functions which may be of independent interest. Precisely, for 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 $\alpha \le\max\{n,\beta^{(\log t)/c}\}$, where $c=c(n,\beta)$ is the unique positive root of the equation $2^c(n^{c/\log\beta}-1)=1$. In particular, our bound implies that $\alpha \le (n\beta)^{\log t}$. We also give examples of polymatroid functions with arbitrarily large $t, n, \alpha$ and $\beta$ for which $\alpha \ge \beta^{(.551 \log t)/c}$. Download Access Level: Public

 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:

@INPROCEEDINGS{Elbassioni2002b,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {Matroid Intersections, Polymatroid Inequalities, and Related Problems},
BOOKTITLE = {Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2420},
PAGES = {143--154},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Warsaw, Poland},
MONTH = {August},
}

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 07:35:26 PM Revisions 4. 3. 2. 1. 0. Editor(s) Christine Kiesel Christine Kiesel Khaled Elbassioni Khaled Elbassioni Khaled Elbassioni Edit Dates 02.05.2007 15:41:01 02.06.2006 15:17:59 04/20/2006 06:42:31 PM 02/22/2005 07:56:38 PM 02/22/2005 07:35:26 PM
Attachment Section

View attachments here: