BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:A Faster Algorithm for Linear Programming and the Maximum Flow Pro
 blem
DTSTART:20150203T160000
DTEND:20150203T170000
DTSTAMP:20260407T112118Z
UID:4ca61c8fb3fb80f8c6592251b65162dd6960e6dfdd082c8e22e4a66b
CATEGORIES:Conferences - Seminars
DESCRIPTION:Yin Tat Lee\, MIT\nAbstract:\nIn this talk\, I will present a 
 new algorithm for solving linear programs. Given a linear program with n v
 ariables\, m > n constraints\, and bit complexity L\, our algorithm runs i
 n Õ(sqrt(n) L) iterations each consisting of solving Õ(1) linear systems
  and additional nearly linear time computation. Our method improves upon t
 he convergence rate of previous state-of-the-art linear programming method
 s which required solving Õ(sqrt(m)L) linear systems. As a corollary\, we 
 achieve a running time of Õ(|E| sqrt(|V|)) for solving the maximum flow p
 roblem on a directed graph with |E| edges\, |V| vertices\, thereby improvi
 ng upon the previous fastest running time Õ(|E|^(3/2)) and Õ(|E| |V|^(2/
 3)).\nThis talk reflects joint work with Aaron Sidford (See http://arxiv.o
 rg/abs/1312.6677 and http://arxiv.org/abs/1312.6713).\nShort Bio:\nYin Tat
  Lee is a PhD student (under Professor Jonathan Kelner) at MIT\, studying 
 theoretical computer science. His areas of research span convex optimizati
 on\, linear programming\, spectral graph theory and algorithmic graph theo
 ry. He is particularly interested in combining convex optimization and com
 binatorial techniques to design fast algorithms for fundamental cut/flow p
 roblems. He is one of the recipients of the Best Paper Award at SODA 2014 
 for an almost-linear-time algorithm for approximate max flow in undirected
  graphs. Recently\, Aaron Sidford and he resolved a long-standing open que
 stion for linear programming\, which gives a faster interior point method 
 and a faster exact min cost flow algorithm. This result receives the Best 
 Paper Award\, as well as the Best Student Paper Award of FOCS 2014.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR