|Discrete Mathematics and Optimization Seminar
Thursday February 16th at 4pm
Title. Integrality Gaps for Throughput Maximization.
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.