Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Matroid Intersections, Polymatroid Inequalities, and Related Problems


Elbassioni,  Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Boros, E., Elbassioni, K. M., Khachiyan, L., & Gurvich, V. (2002). Matroid Intersections, Polymatroid Inequalities, and Related Problems. In Mathematical Foundations of Computer Science 2002 (pp. 143-154). Berlin: Springer. doi:10.1007/3-540-45687-2_11.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-EC9B-8
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) ≥ t_1,\ldots,f_m(X) ≥ 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≥q 1, let α=α(f,t) denote the number of maximal sets X \subseteq V satisfying f(X)< t, let β=β(f,t) be the number of minimal sets X \subseteq V for which f(X) ≥ t, and let n=|V|. We show that α ≤\maxn,β^{(\log t)/c}}, where c=c(n,β) is the unique positive root of the equation 2^c(n^{c/\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 α ≥ β^{(.551 \log t)/c.