MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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
Hide details for Edit History (please click the blue arrow to see the details)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


File Attachment Icon
MFCS02.pdf