speaker: Henry Wolkowicz Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario, Canada

title: Coordinate Shadows of Semi-definite and Euclidean Distance Matrix Completions

MSC: 90C22,


We consider the sets of input data defining feasible semi-definite and Euclidean distance matrix completion problems. We characterize when these sets are closed based on the structure of the underlying graphs, and show that in the presence of boundary data, an intuitive facial reduction technique may drastically reduce the size of the positive semi-definite formulations of these completion problems. We exploit facial reduction based on the cliques of the graph. Chordality of the graph plays an essential role.

collaboration with: Dmitriy Drusvyatskiy, University of Waterloo Gabor Pataki, University of North Carolina at Chapel Hill