[Colloquium] REMINDER: Talk by Hariharan Nayanayan Today

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, April 13, 2009
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Hariharan Naranayan

From:		University of Chicago

Title:    Random Walks on Polytopes and an Affine Interior Point  
Algorithm for Linear Programming

Abstract:     Let K be a polytope in R^n defined by m linear  
inequalities. We give a new Markov Chain algorithm to draw a nearly  
uniform sample from K. The underlying Markov Chain is the first to  
have a mixing time that is strongly polynomial when started from a  
``central'' point x. If s is the supremum over all chords pq passing  
through x of |p-x|/|q-x| and \epsilon is an upper bound on the desired  
total variation distance from the uniform, it is sufficient to take  
O(m n( n log (s m) + log 1/\epsilon)) steps of the random walk. We use  
this result to design an affine interior point algorithm that does a  
single random walk to approximately solve linear programs with high  
probability in polynomial time. The fact that this algorithm has a run- 
time that is provably polynomial is notable since the run-time of the  
analogous deterministic affine algorithm analyzed by Dikin has no  
known polynomial guarantees. This is work with Ravi Kannan.


Refreshments will be served prior to the talk in RY 255.