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.