1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Linear functionals over a polytope are always optimized at a vertex. If you take the base polytope, which is the convex hull of the bases, then all vertices are bases, and so you can use the greedy algorithm. If you take the matroid polytope, which is the convex hull of the independent sets, then all vertices are independent sets, so you can again use the greedy algorithm. $\endgroup$ – Yuval Filmus Dec 28 '17 at 22:48
  • $\begingroup$ @YuvalFilmus That makes sense. So just to confirm, I was confusing/conflating the base polytope $P_{M_{\omega}}$ (only maximal independent subsets are vertices) and the matroid polytope $P_M$ (all independent sets are vertices)? Also if you want to write this as an answer I will/would accept it. $\endgroup$ – Chill2Macht Dec 29 '17 at 17:36
  • 1
    $\begingroup$ It seems that $M_\omega$ is a collection of only some of the bases, so its convex hull is not the entire base polytope. $\endgroup$ – Yuval Filmus Dec 29 '17 at 18:30
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.