Title of presentation:
Semidefinite Programming and Matrix Completion

colloquium talk at the Tutte Colloquium in Dept. Comb. and Opt., Univ. of Waterloo. Friday, June 16, 2000.

(The Abstract (text file):; the presentation (ps file))

This talk is partly based on several papers; principally, on the papers dealing with completion problems. The paper
Positive definite completions of partial {H}ermitian matrices (GRONE, B. and JOHNSON, C.R. and MARQUES de SA, E. and WOLKOWICZ, H.) presents a characterization for completion using chordality of graphs;
while the two papers:
Solving Euclidean distance matrix completion problems via semidefinite programming
present primal-dual interior-point methods for solving approximate completion problems. A summary of these results is presented in
Matrix Completion Problems, in the Handbook of Semidefinite Programming, Kluwer Academic, 2000.

However, the main part of the talk is on work in progress with Abdo Alfakih, A Heuristic for Low Dimensional Realizations of Weighted Graphs. This work deals with a new formulation of the Euclidean Distance Matrix Completion problem. This new formulation allows one to exploit sparsity. The talk also focuses on the problem of low rank solutions, or equivalently, low dimensional realizations of Euclidean matrix completion problems.