# Tag Info

18

It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching). Nick Harvey did his Ph.D thesis ...

6

The connection is that if a you can represent the structure underlying your optimisation problem as matroid, you can use the canonical greedy algorithm to optimise the sum of any positive weight function. If your optimisation goal fits this paradigm, you can solve your problem with the greedy approach. Example Consider the minimum spanning tree problem ...

5

These notes written by Winfried Hochstättler for an MAA short course on matroids look like a good, short, introduction. They also contain references to several longer references on oriented matroids.

2

Let $M$ be a matroid with non-negative weight function $w$ and rank function $r$ (the rank of a set of points $S \subseteq M$ is the maximal size of an independent subset of $S$). Suppose that the matroid has rank $m$. You propose the following algorithm: $S = M$. While $|S| > m$: remove from $S$ a minimum weight element $x$ such that $r(S-x) = m$. ...

2

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

1

Suppose that $\mathcal{F}$ is a nonempty collection of subsets of a finite set $U$ satisfying the following axiom: If $A \in \mathcal{F}$ and $B \subseteq A$ then $B \in \mathcal{F}$. Consider the following algorithm, which gets as input a weight function $w\colon U \to \mathbb{R}_+$ (here $\mathbb{R}_+$ consists of all positive reals): Set $S \gets \... 1 It seems that there is a typo –$v_{i+1} - v_i$should be$v_i - v_{i+1}$. Suppose first that all elements are distinct. Then (using the convention$v_0 = 0\$) $$\sum_{i=1}^{q-1} (v_i-v_{i+1}) n_i(B^*) + v_q n_q(B^*) = \\ \sum_{i=1}^{q-1} i (v_i-v_{i+1}) + q v_q = \\ \sum_{i=1}^q i v_i - \sum_{i=2}^q (i-1) v_i = \sum_{i=1}^q v_i.$$ Consider now the ...

Only top voted, non community-wiki answers of a minimum length are eligible