Great papers: Matroids and the Greedy Algorithm

I’ve decided to read and summarize one great paper a week from this list. This week’s paper is Jack Edmonds‘ 1971 paper Matroids and the Greedy Algorithm.

Summary:

Edmonds starts off by confidently stating:

Many discrete programming algorithms are being proposed. One thing most of them have in common is that they do not work very well.

He focuses on ‘better than finite’ algorithms, particularly for loco problems (linear-objective combinatorial). By this, he means an optimization problem with a linear objective c^T x subject to x \in H. The set H is a collection of real vectors (not necessarily integer or 0-1), though they are often 0-1 vectors. In the 0-1 loco problem, one should choose an optimal cost subset of elements from a ground set E such that the chosen subset belongs to H. Often one represents the chosen subset as a (binary) characteristic vector, where entry e is 1 if element e \in E is chosen to be in the subset (and zero otherwise).

A nice class of problems is the set of ‘matroidal’ problems, where the greedy algorithm is simple and efficient. A matroid M=(E,H) is a pair of sets where E is a (usually finite) ground set of elements and H is a collection of subsets of E satisfying these three conditions:

  • \emptyset \in H,
  • E_1 \subset E_2 \in H implies E_1 \in H, and
  • |E_1|>|E_2| for E_1, E_2 \in H implies that there exists e \in E_1, e \notin E_2 such that E_2 \cup \{ e\}\in H.

The greedy algorithm works by starting with the empty set (which will be feasible if (E,H) is a matroid). In each iteration, we start with E' \in H and add to it the maximum (minimum) cost element e \in E\setminus E' such that E'\cup \{e\} belongs to H. Stop when no single element can be added (i.e., it is maximal). The resulting set is an optimal basis for E.

Consider a matroid defined for a graph G=(V,E) in the following way. Let the edge set E be the ground set, and let H be the collection of all subsets of edges that induce a forest. Applying the greedy matroid algorithm here equates to Kruskal’s minimum spanning tree algorithm.

Matroid polyhedra are particularly interesting. Suppose we want to formulate the matroid problem as a 0-1 program. Let x represent the characteristic vector of a subset of E. It turns out that solutions to the matroid problem are precisely the vertices of the polyhedron defined by the nonnegativity inequalities x_j \ge 0~\forall j \in E and the rank inequalities \sum_{j \in A} x_j \le r(A)~\forall A \subseteq E. Here, r(A) is the rank of A, defined as the cardinality of the largest subset of A that belongs to H.

He mentions yet another elegant result concerning matroid polyhedra. Let v(P) denote the set of vertices of the polyhedron P, and consider matroids M_1 and M_2 defined on the same ground set E with associated polyhedra P_1 and P_2. Then v(P_1 \cap P_2) = v(P_1) \cap v(P_2).

A minor complaint: Despite the paper’s obvious strengths in terms of content, its formatting and structure made it difficult to follow. Each paragraph is numbered–zero to eighty-one–which is distracting. It is also not divided into sections.

Next up: M. Held and R. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees, Operations Research 18 (1970), 1138.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s