CAM colloquium - Friday, April 8
3:30 p.m.
253 Rhodes Hall *****NOTE ROOM CHANGE

Speaker: Daniel Bienstock, Columbia University

 

Title: New Algorithms for the Maximum Throughput Problem

Abstract: The maximum throughput problem, also known as the maximum concurrent flow problem, is the following. We are given a network with capacitated arcs and a set of multicommodity traffic demands to be routed. It may prove impossible to route all the traffic without exceeding the capacities. When this is the case, we wish instead to route an equal percentage of each demand. The objective of the problem is to maximize this percentage.

This problem is of fundamental importance in networking and telecommunications. It may well be the most commonly solved optimization problem in those fields. The problem can be formulated as a linear program. However, large instances (i.e. networks with one thousand or more nodes and many thousand demands) give rise to linear programs that are extremely challenging to unsolvable using state-of-the-art LP software.

Starting in the 1990s, work by many researchers, in particular, Shahrokhi and Matula, Plotkin, Shmoys and Tardos, Grigoriadis and Khachiyan, and others, produced a family of algorithms that compute, for any epsilon > 0, a solution with relative error at most epsilon, by solving at most O(1/epsilon**2) "small" linear programs (for example, shortest path problems). It was theorized that 1/epsilon**2 was a lower bound for any such approximation algorithms.

By using a technique recently developed by Nesterov, we show how O*(1/epsilon) iterations suffice. We will also discuss recent work by Nemirovskii that is related to Nesterov's results. Joint work with Garud Iyengar.

 

Refreshments at 4:30 in 657 Rhodes Hall.