Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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.