Location
Toggle navigation
HOME
INSTITUTE
Mission
Address
Executive Board
Directorate
Scientific Advisory Board
Board of Trustees
NEWS
Press Releases
Awards
Spotlights
Campus Event Calendar
25th Anniversary
Employment
DEPARTMENTS
Algorithms & Complexity
Computer Vision and Machine Learning
Internet Architecture
Computer Grapics
Databases and Information Systems
Research Group Computational Biology
Automation of Logic
PUBLICATIONS
Algorithms & Complexity
Computer Vision and Multimodal Computing
Computer Grapics
Databases and Information Systems
Research Group Computational Biology
Automation of Logic
Research Reports
IMPRS-CS
PEOPLE
SOFTWARE
SERVICES
Joint Administration
- Information Services & Technology
- Building and Technical Support
- Library
- Public Relations
Research Coordination
Equal Opportunities
Care Appointees
Ombudsperson for
Good Scientific Practice
and Doctoral Research
International Office
CS@MPG
CS@SAAR
Computer Science Department,
Saarland University
Max Planck Institute for
Software Systems (MPI-SWS)
German Center for
Artificial Intelligence (DFKI)
Center for Security, Privacy
and Accountability (CISPA)
Graduate School for
Computer Science
Cluster of Excellence (MMCI)
Max Planck Center for Visual
Computing and Communication
Kaiserslautern-Saarbrücken
Computer Science Cluster
IT Incubator
Publications
Home
Intranet
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
Attachment(s)
:
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
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
Attachment Section
Attachment Section
MFCS02.pdf
MFCS02.pdf