Cuts, matrix completions and graph rigidity

Cuts, matrix completions and graph rigidity

0.00 Avg rating0 Votes
Article ID: iaor1999971
Country: Netherlands
Volume: 79
Issue: 1/3
Start Page Number: 255
End Page Number: 283
Publication Date: Oct 1997
Journal: Mathematical Programming
Authors:
Keywords: programming: convex
Abstract:

This paper brings together several topics arising in distinct areas: polyhedral combinatorics, in particular, cut and metric polyhedra; matrix theory and semidefinite programming, in particular, completion problems for positive semidefinite matrices and Euclidean distance matrices; distance geometry and structural topology, in particular, graph realization and rigidity problems. Cuts and metrics provide the unifying theme. Indeed, cuts can be encoded as positive semidefinite matrices (this fact underlies the approximate algorithm for max-cut of Goemans and Williamson) and both positive semidefinite and Euclidean distance matrices yield points of the cut polytope or cone, after applying the functions 1/π arccos(.) or √. When fixing the dimension in the Euclidean distance matrix completion problem, we find the graph realization problem and the related question of unicity of realization, which leads to the question of graph rigidity. Our main objective here is to present in a unified setting a number of results and questions concerning matrix completion, graph realization and rigidity problems. These problems contain indeed very interesting questions relevant to mathematical programming and we believe that research in this area could lead to cross-fertilization between the various fields involved.

Reviews

Required fields are marked *. Your email address will not be published.