[talks] A Agarwal preFPO

[Melissa M Lawson]

 Amit Agarwal will present his preFPO on Monday May 14 at 3:30PM in Room 302 (note room!).

The members of his committee are:  Moses Charikar, advisor; Rob Schapire and Sanjeev 
Khanna (U Penn), readers; Ken Steiglitz and Bob Tarjan, nonreaders.  Everyone is invited
to 
attend his talk.  His abstract follows below.
---------------------------------

Optimization has emerged as a field of central importance for its practical applications
in operations research, physics, chemistry, applied mathematics, and computer science. As
our understanding of optimization has deepened, it has emerged that several important
optimization problems are difficult to solve exactly in reasonable amount of time,
assuming widely believed complexity assumptions. The natural approach in such cases is to
obtain approximate solutions. There is a huge body of work towards designing algorithms
with provable guarantees about their sub-optimality. In general, two kinds of error
estimation techniques have been evolved for such problems: multiplicative and additive. In
the study of approximation algorithms one typically looks for multiplicative approximation
to problems which are NP-hard. On the other hand, results in the field of online
optimization typically have additive errors. The latter work also has connections to
machine learning and statistics.

I will present three results in the broad area of approximate optimization:
(i) The first result is on improved approximation for directed cut problems from joint
work with Noga Alon and Moses Charikar.
(ii) The second result bridges the field of approximation algorithms and network coding
theory. We show that certain integrality gaps studied by the approximation algorithms
community are the same as certain parameters in network coding. This is joint work with
Moses Charikar.
(iii) Finally we present faster algorithms for online optimization with applications to
portfolio management. This is based on papers with Elad Hazan, Robert Schapire, Satyen
Kale, and Adam Kalai.