SCHEDULE -- (You can also see the abstracts for the talks.)

Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems

Wednesday May 15- Friday 17, 1996

to be held at
The Fields Institute
Toronto, Ontario, Canada

Supported jointly by Fields Institute and CRM


  1. Tuesday,
  2. Wednesday, sessions: W1, W2, W3, W4,
  3. Thursday, sessions: R1, R2, R3, R4,
  4. Friday, sessions: F1, F2, F3, F4,

    Tuesday, May 14, 1996

    6:00--8:00PM      Registration and Reception 
                       2nd Floor Fields Institute

    Wednesday, May 15, 1996

    8:15--8:20        Opening Remarks 
    8:20--8:30        Welcome from the Director of the Fields Institute, 
                              John Chadam 
    Session W.1 Chairman: P. Pardalos
    • 8:30-- Monique Laurent
      A connection between positive semidefinite and Euclidean distance matrix completion problems
    • 9:00-- Charles Johnson
      Recent progress on non-positive definite matrix completion problems
    • 9:30-- Stefan Karisch (speaker) and F. Rendl
      Semidefinite Programming and Graph Equipartition
    • 10:00-- Kees Roos (speaker), Tamas Terlaky, Etienne de Klerk
      Initialization in semidefinite programming via a self-dual embbedding

    10:30-10:50-- Break

    Session W.2 Chairman: J. Cheriyan
    • 10:50 -- C. Helmberg (speaker), F. Rendl, R. Weismantel
      Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming
    • 11:20 -- Philip Klein and Hsueh-I Lu (speaker)
      Fast approximation algorithms for some semidefinite relaxations arising from combinatorial optimization problems (principally, MAX CUT and COLORING)
    • 11:50 -- Lieven Vandenberghe (speaker), Stephen Boyd, Shao-Po Wu
      Determinant Maximization with linear matrix inequality constraints

    12:20-1:50-- Lunch

    Session W.3 Chairman: H. Wolkowicz
    • 1:50 -- F. Rendl (speaker) and C. Helmberg
      Large Scale SDP using eigenvalues
    • 2:20 -- Zhi-Quan Luo (speaker) Jos F. Sturm and Shuzhong Zhang
      Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming

    2:50-3:20 -- Break

    Session W.4 Chairman: J. Cheriyan
    • 3:20 -- Gabor Pataki
      Cone-LP's and Semidefinite Programs: Geometry and a Simplex-type Method
    • 3:50 -- J.P. Warners, T. Terlaky(speaker), C. Roos, B. Jansen
      Potential reduction algorithms for structured combinatorial optimization problems
    • 4:20 -- Lorant Porkolab (speaker) and Leonid Khachiyan
      Bounds on Feasible Solutions of Semidefinite Programs

    6:20 -- Conference Reception, at the Fields Institute

    Thursday, May 16, 1996

    Session R.1 Chairman: L. Tuncel
    • 8:30-- Mauricio G.C. Resende (speaker) and Panos Pardalos
      Using linear programming to help solve quadratic assignment problems
    • 9:00-- Michael J. Todd (speaker), Kim Chuan Toh, Reha H. Tutuncu,
      On the Nesterov-Todd direction in semidefinite programming
    • 9:30-- John E. Mitchell
      Using an Interior Point Algorithm in a Cutting Plane Method for Solving Integer Programming Problems
    • 10:00-- Qing Zhao (speaker), Stefan E. Karisch, Franz Rendl, Henry Wolkowicz
      Semidefinite Programming Relaxations for the Quadratic Assignment Problem

    10:30-10:50-- Break

    Session R.2 Chairman: T. Vannelli
    • 10:50 -- Leonid Faybusovich
      Infinite-dimensional semidefinite programming: self-concordant barriers and path-following algorithms for Semidefinite Programming
    • 11:20 -- Chih-Jen Lin and Romesh Saigal (speaker)
      An infeasible start predictor corrector method for semidefinite linear programming
    • 11:50 -- LE THI Hoai An and PHAM DINH Tao (speaker)
      D.c. (difference of convex functions) Optimization: Theory, Algorithms & Aplications

    12:20-1:50-- Lunch

    Session R.3 Chairman: H. Wolkowicz
    • 1:50 -- A. Shapiro
    • 2:20 -- Jos F. Sturm and Shuzhong Zhang (speaker)
      Symmetric primal-dual path following algorithms for SDP

    2:50-3:20 -- Break

    Session R.4 Chairman: P. Pardalos
    • 3:20 -- Boris Mirkin
      Approximation Clustering: A Mine of Semidefinite Programming Problems
    • 3:50 -- Jonas MOCKUS, Audris MOCKUS, Linas MOCKUS (speaker)
    • 4:20 -- Arjan Berkelaar (speaker) and Shuzhong Zhang
      Convergence Issues and Path-following Algorithms for Semidefinite Programming
    • 5:10 -- Dimitris Bertsimas
      Bounds and policies for dynamic optimization via semidefinite and infinite linear programming

    Friday, May 17, 1996

    Session F.1 Chairman: H. Wolkowicz
    • 8:30-- Kees Roos, Tamas Terlaky, Etienne de Klerk (speaker)
      Method of approximate centers for semidefinite programming
    • 9:00-- Zhi-Quan Luo Jos F. Sturm (speaker) and Shuzhong Zhang
      Duality and self-duality for semidefinite and conic convex programming
    • 9:30-- . Goldfarb and K. Scheinberg (speaker)
      Interior Point Trajectories in Semidefinite Programming
    • 10:00-- Ding-zhu Du
      On Floorplan Design and Optimization

    10:30-10:50-- Break

    Session F.2 Chairman: P. Pardalos
    • 10:50 -- Yinyu Ye
      On the complexity of approximating a KKT point of quadratic programming
    • 11:20 -- Manuel A. Nunez (speaker) and Robert M. Freund
      Condition Measures and Properties of the Central Trajectory of a Semidefinite Program
    • 11:50 -- LE THI Hoai An (speaker) and PHAM DINH Tao
      An efficient adapted DCA and Branch-and-Bound algorithm for globally solving large-scale 0-1 quadratic programming problems

    12:20-1:50-- Lunch

    Session F.3 Chairman: T. Vannelli
    • 1:50 -- Jun Gu
      Optimization Algorithms for Satisfiability (SAT) Problem
    • 2:20 -- M. R. Emamy-K.
      How efficient can we maximize threshold pseudo-Boolean functions?

    2:50-3:20 -- Break

    Session F.4 Chairman: L. Tuncel
    • 3:20 -- M. Ramana
      Recognition of Polyhedral Semidefinite Programs
    • 3:50 -- Renato Monteiro
      Primal-Dual Path Following Algorithms for Semidefinite Programming
    • 4:20 -- Yin Zhang
      Some Thoughts on Primal-Dual Interior-Point Methods for Semidefinite Programming
    • 5:10 -- Laura Palagi (speaker) and Stefano Lucidi
      Trust region Problems: Theoretic Results and New Algorithmic Developments

    This directory