Example of greedy algorithm for matroid optimization?

200 Views Asked by At

Let $M=(E,\mathcal I)$ with $|E|=n$ be a matroid and $c\in\mathbb R^n$, then the optimization problem \begin{align} \max_T &\quad\sum_{j\in T} c_j\\ \mathrm{s.t.} &\quad T\in\mathcal I \end{align} has the integer programming formulation \begin{align} \max &\quad\sum_{j\in E} c_jx_j\\ \mathrm{s.t.} &\quad \sum_{j\in S} x_j\leqslant r(S),\quad \forall S\subset E\\ &\quad x\in\{0,1\}^n \end{align} where for $T\subset E$, $$ x_j = \begin{cases} 1,& j\in T\\ 0,& j\notin T\end{cases} $$ and $r(S)$ is the rank of $S$ (the size of a maximal independent set contained in $S$).

There is a greedy algorithm to solve this problem, which sorts the $c_j$ by non-decreasing order and iteratively adds elements of $E$ in order of the $c_j$, so long as the resulting set is within $\mathcal I$. But I am not sure how to actually apply this algorithm to a problem (differing notation between sources is a bit frustrating).

To be more concrete, let $G=(V,E)$ with $V=\{a,b,c,d\}$ and $E=\{ab, ac, ad, bc, cd\}$, then consider the matroid $(E,\mathcal I)$ where $\mathcal I$ is the collection of all subsets of edges that are acyclic (the cycle matroid of $G$). Let the cost vector be $$ (c(ab), c(ac), c(ad), c(bc), c(cd)) = \pmatrix{1, 1, 2, 2, 3}. $$ How can I apply the greedy algorithm to solve the maximization problem for this matroid?