Study of Combinatorial Optimization

Abstract

The primal-dual method is a standard tool in the design of algorithms for combinato- rial optimization problems. It is a very powerful method. This method can be used to obtain a good approximation algorithm from which we can get a good combinatorial algorithm. It can also be used to prove good performance for combinatorial algo- rithms. Max- ow Min-cut is a very nice example of primal dual method. we would like to interpret its primal, then obtain its dual, interpret the dual and then prove the max- ow min-cut theorem using the strong duality.