An Analysis on Various Techniques, Properties and Algorithms of Linear Programming In Combinatorial Optimization |

ABSTRACT:

We study techniques, approximation algorithms, structuralproperties and lower bounds related to applications of linear programs incombinatorial optimization. The following Steiner tree problem is central: given a graph with adistinguished subset of required vertices, and costs for each edge, find aminimum-cost subgraph that connects the required vertices. We also investigatethe areas of network design, multicommodity flows, and packing/covering integerprograms. All of these problems are NP-complete so it is natural to seekapproximation algorithms with the best provable approximation ratio. Overall,we show some new techniques that enhance the already-substantial corpus ofLP-based approximation methods, and we also look for limitations of thesetechniques.