Cuts, matrix completions and graph rigidity
Laurent, Monique

Data: 1997
Resum: 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 approximative 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/(pi) arccos(. ) or V¯. 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 yield to cross-fertilization between the various fields involved. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Cut ; Positive semidefinite matrix ; Euclidean distance matrix ; Matrix completion ; Metric polyhedron ; Graph rigidity
Publicat a: Mathematical Programming, vol. 79 n. 1-3 (1997) p. 255-283, ISSN 0025-5610

29 p, 1.7 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir