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