DIMACS Workshop on Algorithmic Challenges in Optimization, Game Theory and

Computer Science: in Memory of Leo Khachiyan

 (Organizers: Endre Boros and Vladimir Gurvich)

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

 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, Bethlehem, PA

  

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

 

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 the application of semidefinite programming to discrete optimization

                                    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