| COMPUTER SCIENCE/DISCRETE MATH II | |
| Topic: | Approximating Functions in Logarithmic Space and Time: A "Plug & Play" Approach |
| Speaker: | Nir Halman |
| Affiliation: | MIT and Member, School of Mathematics |
| Date: | Tuesday, May 27 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
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)