Return to Colloquia & Seminar listing
Fast Approximation Schemes for Packing and Covering Linear Programs
OptimizationSpeaker: | Prof. Lisa Fleischer, Carnegie Mellon University |
Location: | 693 Kerr |
Start time: | Tue, Jun 1 2004, 9:00AM |
In an effort to find good solutions quickly to very large scale linear programs, there is a desire for algorithms that are faster and less memory intensive than standard LP codes and algorithms. In response, researchers have developed approximation schemes for special classes of LPs. The run time of these schemes has a smaller dependence on the size of the problem than standard LP algorithms, with the tradeoff that the dependence on the level of accuracy is higher. Thus these schemes are useful (in theory and in practice) for finding approximately optimal solutions to very large problems - for example, problems arising in telecommunications. We present faster approximation schemes for positive packing and covering linear programs, and discuss applications to multicommodity flows, generalized flows, network design, and VLSI design.