Discrete Mathematics and Optimization Seminar

Bruce Shepherd
Bell Laboratories
Thursday February 16th at 4pm
Burnside 934

Title. Integrality Gaps for Throughput Maximization.

Abstract. Most attacks on combinatorial optimization problems implicitly involve finding a convex region,
typically but not necessarily arising from an LP, that closely hugs (approximates) a region associated
with the combinatorial objects being optimized. We outline this approach and see its application to
finding a maximum collection of edge-disjoint paths, a problem central to network routing, VLSI
design and scheduling. We show recent results (with C. Chekuri and S. Khanna) on estimating the
"integrality gap" of a natural LP relaxation for edge-disjoint paths.