!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                                       
                  B O S T O N   U N I V E R S I T Y
                                   
                     Computer Science Department
                                   
                         C O L L O Q U I U M
                                   
                                   
                   Smoothed Analysis of Algorithms:
       Why the Simplex Algorithm Usually Takes Polynomial Time *
                                   
                            Shang-Hua Teng
                             Akamai/UIUC
                                   
                   Friday May 4th, 2001 @ 11:00 AM
                      (Coffee served at 10:45AM)
                                   
                        Seminar Room / MCS 135
                                   
                               Abstract

Theorists  have  been  challenged   by  the  existence  of  remarkable
algorithms that are known by  scientists and engineers to work well in
practice,   but   whose   theoretical   analyses   are   negative   or
inconclusive. The root  of the problem is that  algorithms are usually
analyzed in one  of two ways: by worst-case  or average-case analysis. 
The  former can  improperly  suggest that  an  algorithm will  perform
poorly, while the  latter can be overly optimistic  because the random
inputs it  considers can bear little resemblance  to those encountered
in practice.  We propose  an analysis that  we call  smoothed analysis
that  can  help explain  the  success  of  many algorithms  that  both
worst-case and  average-case cannot. In smoothed  analysis, we measure
the performance  of an algorithm under slight  random perturbations of
arbitrary inputs. In particular, we consider Gaussian perturbations of
inputs to algorithms that take real and complex inputs, and we measure
the running  time of  algorithms in  terms of the  input size  and the
variance of the perturbations. We  show that the simplex algorithm has
polynomial smoothed complexity.

The  simplex algorithm  is the  classic example  of an  algorithm that
performs  well in  practice but  takes exponential  time in  the worst
case. In  the 1980's  the simplex algorithm  was shown to  converge in
expected polynomial  time on  various distributions of  random inputs,
most notably  by Borgwardt  and Smale. However,  the last 20  years of
research  in probability and  numerical analysis  have taught  us that
these random  instances have very  special properties that  one should
not expect to find in practice.

For every  matrix A with  entries of absolute  value at most  1, every
vector c, and every  vector b whose entries are 1 or  -1, we show that
the  simplex  algorithm  using  the  shadow-vertex  pivot  rule  takes
expected time polynomial in 1/sigma and  the sizes of A and c to solve

  minimize c'x
  s.t (A + \sigma G) x <= b

If  A  is  well-scaled,  then  the  solution to  this  program  is  an
approximation to the original.


* This is joint work with Daniel Spielman of MIT.

Host:  Azer Bestavros (bestavros@cs.bu.edu)

-----------------------------------------------------------------------
For more information and directions see http://cs-www.bu.edu/colloquium
-----------------------------------------------------------------------