TY - GEN
T1 - Matroid intersections, polymatroid inequalities, and related problems
AU - Boros, Endre
AU - Elbassioni, Khaled
AU - Gurvich, Vladimir
AU - Khachiyan, Leonid
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84957037513&partnerID=8YFLogxK
U2 - 10.1007/3-540-45687-2_11
DO - 10.1007/3-540-45687-2_11
M3 - Conference contribution
AN - SCOPUS:84957037513
SN - 3540440402
SN - 9783540440406
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 143
EP - 154
BT - Mathematical Foundations of Computer Science 2002 - 27th International Symposium, MFCS 2002, Proceedings
A2 - Diks, Krzysztof
A2 - Rytter, Wojciech
A2 - Rytter, Wojciech
PB - Springer Verlag
T2 - 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002
Y2 - 26 August 2002 through 30 August 2002
ER -