Can LP for matroid polytopes be solved using the greedy algorithm?

Question

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, although it's not done often in practice, the ellipsoid algorithm).

Matroids are well known for the property that the greedy algorithm is optimal if and only if it is performed for a weight function defined on the bases of a matroid. (Or something similar.)

Question: In special cases where we can somehow create a correspondence between vertices of a polytope and bases of a matroid, does the greedy algorithm provide a solution for LP?

The answer to this seems like it might be yes based on the paper The Bergman Complex of a Matroid and Phylogenetic Trees by Federico Ardila and Caroline J. Klivans. However, the exposition does not confirm or deny this suspicion explicitly, and without an explicit statement either way, combined with the fact I am not 100% certain I understand the definitions, I am still unsure if it is true or not. Below I quote the portion with the relevant definitions and hint:

Let $M$ be a matroid of rank $r$ on the ground set $[n] = \{1,2,...,n\}$, and let $\omega \in \mathbb{R}^n$. Regard $\omega$ as a weight function on $M$, so that the weight of a basis $B=\{b_1,...,b_r\}$ of $M$ is given by $$\omega_B =\omega_{b_1} + \omega_{b_2} +\cdots+\omega_{b_r} \,.$$ Let $M_{\omega}$ be the collection of bases of $M$ having minimum $\omega$-weight... we can understand $M_{\omega}$ in terms of the matroid polytope. [emphasis mine] We will use the following characterization of matroid polytopes, due to Gelfand and Serganova:

Theorem. [6, Theorem 1.11.1] Let $S$ be a collection of $r$-subsets of $[n]$. Let $P_S$ be the polytope in $\mathbb{R}^n$ with vertex set $\{e_{b_1} +\cdots+e_{b_r} |\{b_1,\dots,b_r\} \in S\}$, where $e_i$ is the $i$-th unit vector. Then $S$ is the collection of bases of a matroid if and only if every edge of $P_S$ is a translate of the vector $e_i − e_j$ for some $i, j \in [n]$.

Let $P_M$ be the matroid polytope of $M$. We can now think of $\omega$ as a linear functional in $\mathbb{R}^n$. The bases in $M_{\omega}$ correspond to the vertices of $P_M$ which minimize the linear functional $\omega$. [emphasis mine] Their convex hull is $P_{M_{\omega}}$, the face of $P_M$ where $\omega$ is minimized. It follows that the edges of $P_{M_{\omega}}$, being edges of $P_M$ also, are parallel to vectors of the form $e_i − e_j$. Therefore $M_{\omega}$ is the collection of bases of a matroid.

Answer 1

You can associate with each matroid two polytopes in $\mathbb{R}^n$, where $n$ is the size of the universe over which the matroid is defined:

• The matroid polytope is the convex hull of the characteristic vectors of all independent sets.
• The base polytope is the convex hull of the characteristic vectors of all bases (maximal independent sets).

The maximum of a linear function over a polytope is always attained (not necessarily uniquely) at a vertex. Therefore maximizing a linear function over a base polytope is like maximizing it over the collection of bases, for which the greedy algorithm can be used. The same goes for the matroid polytope, with the necessary changes.