DIMACS Workshop on Algorithmic Challenges in Optimization, Game Theory and Computer Science: in Memory of Leo Khachiyan

March 9 - 10, 2009
DIMACS Center, CoRE Building, Rutgers University

Organizers:

Endre Boros, Director of RUTCOR, Endre.Boros at rutcor.rutgers.edu

Vladimir Gurvich, RUTCOR, gurvich at rutcor.rutgers.edu

Workshop Program:

Monday, March 9, 2009

 8:30 -  9:00  Breakfast and Registration
 
 9:00 - 10:00  Opening Remarks by Fred Roberts, Eric Allender, Mike Grigoriadis, Vasek Chvatal, 
               Bahman Kalantari, and Vladimir Gurvich

10:00 - 10:30  Coffee Break

10:30 - 11:00  Fast Approximation Schemes for Structured Programs and Matrix Games
               Mike Grigoriadis, Rutgers University

11:00 - 11:30  Acceleration by Randomization:Randomized First Order Algorithms for Large-scale Convex Optimization
               Arkadi Nemirovski, Georgia Institute of Technology

11:30 - 12:00  Beating Simplex for Fractional Packing and Covering Linear Programs
               Neal Young, University of California - Riverside

12:00 - 12:30  Parameterized Approximation Scheme for the Multiple Knapsack Problem
               Klaus Jansen, University of Kiel, Germany

12:30 -  2:00  Lunch

 2:00 -  2:30  Fast Gradient Methods for Network Flow Problems
               Yurii Nesterov, Catholic University of Louvain

 2:30 -  3:00  Matrix Scaling in Linear and Convex Programming
               Bahman Kalantari, Rutgers University

 3:00 -  3:30  Three Decades of Polynomial Time Algorithms for LP
               Tamas Terlaky, Lehigh University

 3:30 -  4:00  Coffee Break

 4:00 -  4:30  On Complexity of Algorithmic Linear Algebra Problems in Exponential Dimension
               Misha Vyalyi, Dorodnitsyn Computing Center, Moscow

 4:30 -  5:00  The Negative Cycles Polyhedron and Hardness of Testing Polyhedral Properties
               Khaled Elbassioni, Max-Planck Institute, Saarbrucken, Germany

 5:00 -  7:00  Reception

Tuesday, March 10, 2009

 8:30 -  9:00  Breakfast and Registration

 9:00 -  9:30  Bilinear Optimality Constraints for the Cone of Positive Polynomials and Related Cones
               Farid Alizadeh, Rutgers University

 9:30 - 10:00  Product rules in Semidefinite Programming
               Mario Szegedy, Rutgers University

10:00 - 10:30  Could Exact SDP be a Computationally Hard Problem?
               Sergei Tarasov, Dorodnitsyn Computing Center, Moscow

10:30 - 11:00  Coffee Break

11:00 - 11:30  Recent Progress in Algorithms and Applications for Semidefinite Programming
               Miguel Anjos, Waterloo University

11:30 - 12:00  HIPCUT - A Hybrid Interior-point Cutting-plane Method for Integer Programming
               Alexander Engau, Waterloo University

12:00 -  1:30  Lunch

 1:30 -  2:00  Accuracy Certificates for Computational Problems with Convex Structure
               Uri Rothblum, The Technion

 2:00 -  2:30  A Modifed Frank-Wolfe Algorithm for Computing Minimum-Area Enclosing
               Ellipsoidal Cylinders: Theory and Algorithms
               Selin Damia Ahipasaoglu, Cornell University

 2:30 -  3:00  Algorithmic Challenges in Risk Averse Optimization
               Andrzej Ruszczynski, Rutgers University

 3:00 -  3:30  Coffee Break

 3:30 -  4:00  Computational Aspects of Monotone Dualization
               Kazuhisa Makino, University of Tokyo

 4:00 -  4:30  Strongly Subexponential Algorithms for Simple Stochastic Games, 
               Parity Games, Mean Payoff Games and Discounted Payoff Games
	       Nir Halman, Massachusetts Institute of Technology

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage