Theory Lunch Seminar

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • JONAH SHERMAN
  • Ph.D. Student
  • Electrical Engineeirng and Computer Sciences
  • University of California at Berkeley
Seminars

Breaking the l_infinity Regularization Barrier: Approximating Undirected Multicommodity Flow in Nearly-Linear Time

Regularization is one of the most powerful tools in continuous optimization, yet existing approaches using strong-convexity fail for several important problems due to the infamous "l_infinity barrier". In this talk, we show strong-convexity may be relaxed to a weaker notion of "area-convexity", for which those barriers do not apply. Using area-convex regularization, we obtain a fast algorithm for approximately solving matrix inequality systems AX <= B over right-stochastic matrices X. By combining that algorithm with recent work on maximum-flow, we obtain a nearly-linear time approximation algorithm for maximum concurrent flow in undirected graphs.

For More Information, Please Contact: 
Keywords: