Event Detail

Event Type: 
Applied Mathematics and Computation Seminar
Date/Time: 
Friday, October 29, 2010 - 05:00
Location: 
GLK 113

Speaker Info

Institution: 
EECE, OSU
Abstract: 

We present a framework for designing polynomial-time approximation
schemes for network design problems such as Steiner tree and 2-edge
connectivity in planar graphs. For a fixed epsilon, a polynomial-time
approximation scheme finds, in polynomial time, a solution whose value
is within 1+epsilon of the optimal solution.

In this talk I will overview the framework and discuss how to use it
to solve a variety of connectivity problems.