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

Advancements in Linear Programming Techniques for Combinatorial Optimization Problems

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.