[home] - [up] |
Abstract: We determine the maximal gap between the optimal values of an integer program and its linear programming relaxation, where the matrix and cost function are fixed but the right hand side is unspecified. Our formula involves irreducible decomposition of monomial ideals. The gap can be computed in polynomial time when the dimension is fixed. (Joint work with Serkan Hosten, math.OC/0301266)
Colloquium - 16:00
Abstract: The Internet is a complex network resulting from distributed growth without central control. The structure of this network, viewed on the level of autonomous systems (subnetworks under separate administrative control), is usually represented as a graph whose edges can be classified according to economic relationships. In this talk, we discuss properties of these Internet graphs, describe algorithmic problems that are encountered in their investigation, and present approximation algorithms for some of these problems. In particular, we give a 2-approximation algorithm for a new NP-hard min-cut problem arising in this context.
Parts of the talk are based on joint work with Alexander Hall, Polly Huang, Thomas Schank, and Danica Vukadinovic.