# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Matroid Intersections, Polymatroid Inequalities, and Related Problems

##### 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

##### Citation

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

##### 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) ≥ 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.