
Semidefinite Programming and InteriorPoint Approaches for Combinatorial
Optimization Problems
SCHEDULE 
(You can also see the abstracts for the talks.)
May 15 Friday 17, 1996
to be held at The Fields Institute, Toronto, Ontario,
Canada
Supported jointly by Fields
Institute and CRM
Tuesday, May 14, 1996
6:008:00PM Registration and Reception
2nd Floor Fields Institute
Wednesday, May 15, 1996
8:158:20 Opening Remarks
8:208: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 nonpositive 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 selfdual embbedding
10:3010: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 HsuehI 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, ShaoPo Wu
Determinant Maximization with linear matrix inequality constraints
12:201:50 Lunch
Session W.3 Chairman: H. Wolkowicz

1:50  F. Rendl (speaker) and C. Helmberg
Large Scale SDP using eigenvalues

2:20  ZhiQuan Luo (speaker) Jos F. Sturm and
Shuzhong Zhang
Superlinear Convergence of a Symmetric PrimalDual Path Following
Algorithm for Semidefinite Programming
2:503:20  Break
Session W.4 Chairman: J. Cheriyan

3:20  Gabor Pataki
ConeLP's and Semidefinite Programs: Geometry and a Simplextype
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 NesterovTodd 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:3010:50 Break
Session R.2 Chairman: T. Vannelli

10:50  Leonid Faybusovich
Infinitedimensional semidefinite programming: selfconcordant barriers
and pathfollowing algorithms for Semidefinite Programming

11:20  ChihJen 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:201:50 Lunch
Session R.3 Chairman: H. Wolkowicz

1:50  A. Shapiro
SECOND ORDER OPTIMALITY CONDITIONS AND STABILITY ANALYSIS OF SEMIDEFINITE
PROGRAMS

2:20  Jos F. Sturm and Shuzhong Zhang (speaker)
Symmetric primaldual path following algorithms for SDP
2:503: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)
BAYESIAN APPROACH TO COMBINATORIAL OPTIMIZATION

4:20  Arjan Berkelaar (speaker) and Shuzhong Zhang
Convergence Issues and Pathfollowing 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 ZhiQuan Luo Jos F. Sturm (speaker) and Shuzhong
Zhang
Duality and selfduality for semidefinite and conic convex programming

9:30 . Goldfarb and K. Scheinberg (speaker)
Interior Point Trajectories in Semidefinite Programming

10:00 Dingzhu Du
On Floorplan Design and Optimization
10:3010: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 BranchandBound algorithm for globally
solving largescale 01 quadratic programming problems
12:201:50 Lunch
Session F.3 Chairman: T. Vannelli
1:50  Jun Gu
Optimization Algorithms for Satisfiability (SAT) Problem 2:20  M.
R. EmamyK.
How efficient can we maximize threshold pseudoBoolean functions?
2:503:20  Break
Session F.4 Chairman: L. Tuncel
3:20  M. Ramana
Recognition of Polyhedral Semidefinite Programs
3:50  Renato Monteiro
PrimalDual Path Following Algorithms for Semidefinite Programming
4:20  Yin Zhang
Some Thoughts on PrimalDual InteriorPoint Methods for Semidefinite
Programming
5:10  Laura Palagi (speaker) and Stefano Lucidi
Trust region Problems: Theoretic Results and New Algorithmic Developments

