Algorithms and Complexity Seminar

Monday, May 12, 2008, 4:00-5:15pm in 32-G575.

Approximating Functions in Logarithmic Space and Time: A "Plug & Play" Approach

Nir Halman (MIT)

We consider several natural problems related to the design of approximation algorithms and the analysis of their error bounds. We define a set of sufficient conditions on a function $f:D-->R^+$ and its domain $D$, so that we can construct good approximations for it in space, time, and number of queries, which are all polylogarithmic in $|D|$ and $\max f(x)$.

Using our ideas we construct a meta algorithm for obtaining Fully Polynomial Approximation Schemes (FPTASs) for combinatorial optimization problems on several families of directed acyclic graphs.

Our results are given in a modular way, as a set of ``ready-made" algorithms and computational rules, so that future (and past) approximation algorithms will be simplified by using them.

Joint work with James Orlin (MIT)

Host: Ronitt Rubinfeld

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)