============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

                  Tarde de Algoritmos 
============================================================
Título:      Competitive algorithms for incremental 
             optimization problems

Palestrante: David P. Williamson
             Cornell University

Hora e Data: 15h30, segunda-feira, 09 de novembro de 2009

Local:       Auditório Antonio Gilioli Bloco A

Resumo:

In incremental optimization problems, choices we make in the
future are  constrained by those  we have made in  the past.
The canonical  example of  this is the  incremental k-median
problem, a  variant on  the k-median problem,  introduced by
Mettu and Plaxton.  If  we have already opened k facilities,
and now  wish to open  k' > k  facilities, we may  not close
facilities we have already  opened.  Hence the output of the
incremental k-median problem is simply a sequence of all the
facilities; if  we wish  to open k  facilities, we  open the
first k  in the sequence.  Somewhat  surprisingly, Mettu and
Plaxton showed that it is  possible to find a good sequence,
in the sense that for  any k, opening the first k facilities
is within a constant factor of the best possible solution to
the k-median problem.

In  this  talk, I  will  show  a  very general  approach  to
incremental problems that  are conceptually simple and leads
to the  best known performance guarantees for  many of these
problems,  including  hierarchical  clustering problems.   I
will  also discuss  some experimental  work that  shows that
these algorithms perform much  better in practice than their
theoretical