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,
abstract:
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