Kyoto-Montreal research collaboration on discrete optimization and its applications

Project Leaders:

David Avis and Kazuo Iwama

Principal members:

Kyoto: Marco Cuturi, Satoru Iwata, Naoki Katoh, Hiroshi Nagamochi, Shin-ichi Tanigawa
Montreal: Miguel F. Anjos, Luc Devroye, Bruce Reed, Bruce Shepherd, Adrian Vetta


Main Events:

July-September 2012:  Working group on discrete optimization

Location: GERAD
Organizers: M. F. Anjos and D. Avis

April-July 2012: Project start-up in Kyoto: Working group on linear and integer programming

Location: Kyoto University
Organizers: D. Avis and  N. Katoh

January-April 2012: Project start-up in Montreal: Working group on computing a Nash equilibrium and on evacuation models

Location: GERAD
Organizers: M. F. Anjos and D. Avis

Related Events:

August 27-September 7 2012:  MLSS '12 Kyoto: 21st Machine Learning Summer School

Project summary:

Discrete optimization is a branch of computer science and applied mathematics which has shown remarkable theoretical and practical development in recent years. It combines the techniques of combinatorial analysis, linear programming and the theory of algorithms with the goal of solving optimization problems with discrete decision variables. We will consider the five subprojects below:

  1. Design, development and analysis of parallel tree search algorithms
  2. Efficient generation of molecules in biology and chemistry
  3. Generation of a Nash equilibrium by the primal-dual interior point method
  4. Application of polyhedral computation to machine learning
  5. Discrete multiflows in networks
Project Financing: N.S.E.R.C. and J.S.P.S.