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 -