🚀 go-pugleaf

              The International Computer Science Institute
                     is pleased to present a talk:

                  Tuesday, August 11, 1992  3:300 p.m.

                               EMO WELZL
                       Freie Universitaet Berlin
                                Germany

               ``Recent Results on Linear Programming
                          and Related Problems''

           Recent  years  have  brought  some  progress   in   the
      knowledge  of  the  complexity  of linear programming in the
      unit cost (real RAM) model}, and the best  result  known  at
      this point is a randomized ``combinatorial'' algorithm which
      computes the solution for d variables and n constraints with
      expected  $O(d^2  n  + e^{O(\sqrt{d \log d})}\log n)$ arith-
      metic operations. The bound  relies  on  two  algorithms  by
      Clarkson,  and  the  subexponential algorithms due to Kalai,
      and to Matousek, Sharir & Welzl.

           In this talk we review some of  the  recent  algorithms
      with their analysis. We indicate how these algorithms can be
      applied to a number  of  non-linear  optimization  problems,
      including  the computation of the smallest enclosing ball of
      n points in d-space (Sylvester's problem), and the  computa-
      tion  of  the  distance between two convex polytopes (with n
      vertices or n facets) in d-space.  The  analysis  for  these
      extensions  relies  also on Gaertner's recent subexponential
      bound for so-called abstract optimization problems.


        This talk will be held in the Main Lecture Hall at ICSI.
          1947 Center Street, Sixth Floor, Berkeley, CA 94704
       (On Center between Milvia and Martin Luther King Jr. Way)

       ----------------------------------------------------------
       Requests to be added to or deleted from the "talk" mailing
       list should be directed to talk-request@icsi.Berkeley.EDU.
       ----------------------------------------------------------