Linear Programming

Even more general is linear programming (LP): $Ax \le b$, maximize cx.

Example:

• One variable for each edge, constrained to be between zero (white) and one (blue).
• Constraint for each node: sum of value of variables on incident edges must be no more than one (matching property).
• Maximize sum of edges (number of edges in matching).

In spite of the lack of an integrality constraint, the value of this linear program is equal to the size of the maximum matching.

Can solve network flow problems this way, as well as some tricky generalizations.

Theoretically efficient LP algorithms (ellipsoid, interior point) are very complex. Practical LP algorithm (simplex) is inefficient in the worst case. Very good commercial implementations exist!