**********************************************************************************
RUTCOR Seminar - Thursday, May 1st, 2008
**********************************************************************************

SPEAKER:            Nir Halman
  
AFFILIATION:        Department of Civil and Environmental Engineering, MIT

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

TIME:                    1:30pm

LOCATION:           RUTCOR Building - Room 166, Rutgers University,
                            Busch Campus, Piscataway, NJ

ABSTRACT:         
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 nonnegative
integer-valued oracle function f, and on its domain D, so that we can 
construct good approximations for f in space, time, and number of 
queries, which are all polylogarithmic in |D| and max f(x).
We consider the same problem in which we have access only to an
approximation oracle of it. We also consider approximations of
functions derived from operations on two approximated functions.
Using our ideas we construct a meta algorithm for obtaining almost
optimal solutions 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 may be simplified by using them.

 Joint work with James Orlin (MIT).