Application 2: Directed Graphs Let A be the incidence matrix of a directed graph.
Each row i represents a vertex v(i),
and each column j represents an edge e(j).
A(ij) = +1 if vertex v(i) is the tail of edge e(j).
A(ij) = -1 if vertex v(i) is the head of edge e(j).
A(ij) = 0 otherwise. The incidence matrix A of a directed graph is totally unimodular. Consequences:
The max-flow problem (even min-cost flow) is polynomial time solvable.
Max-flow-min-cut theorem follows from the LP-duality theorem.
Simplex Method Simplex Algorithm:
Start from an arbitrary vertex.
Move to one of its neighbours
which improves the cost. Iterate. For combinatorial problems, we know that vertex solutions correspond
to combinatorial objects like matchings, stable matchings, flows, etc. So, the simplex algorithm actually defines a combinatorial algorithm for these problems.
Simplex Method For example, if you consider the bipartite matching polytope and
run the simplex algorithm, you get the augmenting path algorithm. The key is to show that two adjacent vertices are differed by an augmenting path. Recall that a vertex solution is the unique solution of n linearly independent inequalities. So, moving along an edge in the polytope means to replace one tight inequality by another one. There is one degree of freedom and this corresponds to moving along an edge.
Summary How to prove a linear program gives integer optimal solutions? How to model a combinatorial problem as a linear program. Prove that every vertex solution is integral.
By convex combination method.
By linear independency of tight inequalities.
By totally unimodular matrices.
By shifting technique. See the geometric interpretation of linear programming.
Polynomial Time Solvable Problems Bipartite matchings General matchings Maximum flows Stable matchings Shortest paths Minimum spanning trees Minimum Cost Flows Linear programming Submodular Flows Weighted Bipartite matchings Graph orientation Matroid intersection Packing directed trees Connectivity augmentation
Summary How to obtain min-max theorems of combinatorial problems? LP-duality theorem, e.g. max-flow-min-cut, max-matching-min-vertex-cover. See combinatorial algorithms from the simplex algorithm,
and even give an explanation for the combinatorial algorithms
(local minimum = global minimum).
Comments