Matroid intersections, polymatroid inequalities, and related problems

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

Given m matroids M1,…, Mm 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 f1(X) ≥ t1,…, fm(X) ≥ tm with quasi-polynomially bounded right hand sides t1,…, tm, all minimal feasible solutions X ⊆ 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 ≥ 1, let α = α(f, t) denote the number of maximal sets X ⊆ V satisfying f(X) < t, let β = β(f, t) be the number of minimal sets X ⊆ V for which f(X) ≥ t, and let n = |V|. We show that α ≤ max{n, β(log t)/c}, where c = c(n, β) is the unique positive root of the equation 2c(nc/ log β − 1) = 1. In particular, our bound implies that α ≤ (nβ)log t. We also give examples of polymatroid functions with arbitrarily large t, n, α and β for which α = β(1−o(1)) log t/c.

Original languageBritish English
Title of host publicationMathematical Foundations of Computer Science 2002 - 27th International Symposium, MFCS 2002, Proceedings
EditorsKrzysztof Diks, Wojciech Rytter, Wojciech Rytter
PublisherSpringer Verlag
Pages143-154
Number of pages12
ISBN (Print)3540440402, 9783540440406
DOIs
StatePublished - 2002
Event27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002 - Warsaw, Poland
Duration: 26 Aug 200230 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2420
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002
Country/TerritoryPoland
CityWarsaw
Period26/08/0230/08/02

Fingerprint

Dive into the research topics of 'Matroid intersections, polymatroid inequalities, and related problems'. Together they form a unique fingerprint.

Cite this