14 - Summary

Summary

We have described an iterative method that is versatile in its applicability to showing several results in exact optimization and approximation algorithms. The key step in applying this method uses the elementary Rank Lemma to show sparsity of the support of extreme point solutions for a wide variety of problems. The method follows a natural sequence of formulating a tractable LP relaxation of the problem, examining the structure of tight constraints to demonstrate an upper bound on the rank of the tight subsystem defining the extreme point, using the Rank Lemma to imply an upper bound on the support, and finally using this sparsity of the support to find an element in the support with high (possible fractional) value.

The two key steps in the method are upper bounding the rank of the tight constraints and using the sparsity of the support to imply a high-valued element. Various uncrossing techniques in combinatorial optimization are very useful in the first step. However, new ideas are typically required in the second step, which can be usually carried out with a “token charging” argument to prove by contradiction the presence of a high-value element in the support: Assign a set number, k, of tokens to each support variable (now assumed to be low valued for contradiction) and redistribute these tokens so as to collect k tokens per tight constraints and show some leftover tokens for the contradiction.