Realizing Euclidean distance matrices by sphere intersection

被引：9

作者：

Alencar, Jorge ^{[1
]}

Lavor, Carlile ^{[2
]}

Liberti, Leo ^{[3
]}

机构：

[1] Inst Fed Educ Ciencia & Tecnol Sul Minas Gerais, Inconfidentes, MG, Brazil

[2] Univ Estadual Campinas, IMECC UNICAMP, BR-13081970 Campinas, SP, Brazil

[3] Ecole Polytech, CNRS LIX, F-91128 Palaiseau, France

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 256卷

基金：

巴西圣保罗研究基金会;

关键词：

Distance geometry; Sphere intersection; Euclidean distance matrix; Embedding dimension; GEOMETRY;

D O I：

10.1016/j.dam.2018.06.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper presents the theoretical properties of an algorithm to find a realization of a (full) n x n Euclidean distance matrix in the smallest possible embedding dimension. Our algorithm performs linearly inn, and quadratically in the minimum embedding dimension, which is an improvement w.r.t. other algorithms. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：5 / 10

页数：6

共 15 条

[1]

Alencar J., 2015, ELECT NOTES DISCRETE, V50, P397, DOI [10.1016/j.endm.2015.07.066, DOI 10.1016/J.ENDM.2015.07.066]

[2] Assigned and unassigned distance geometry: applications to biological molecules and nanostructures [J].

Billinge, Simon J. L. ;

Duxbury, Phillip M. ;

Goncalves, Douglas S. ;

Lavor, Carlile ;

Mucherino, Antonio .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2016, 14 (04) :337-376

[3]

Coope I., 2000, ANZIAM J, V42, pC461

[4]

Cox T.F., 2001, MULTIDIMENSIONAL SCA

[5]

Dattorro J., 2010, Convex optimization & Euclidean distance geometry

[6] Fast linear algebra is stable [J].

Demmel, James ;

Dumitriu, Ioana ;

Holtz, Olga .

NUMERISCHE MATHEMATIK, 2007, 108 (01) :59-91

[7] Euclidean Distance Matrices [J].

Dokmanic, Ivan ;

Parhizkar, Reza ;

Ranieri, Juri ;

Vetterli, Martin .

IEEE SIGNAL PROCESSING MAGAZINE, 2015, 32 (06) :12-30

[8] The discretizable molecular distance geometry problem [J].

Lavor, Carlile ;

Liberti, Leo ;

Maculan, Nelson ;

Mucherino, Antonio .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2012, 52 (01) :115-146

[9]

Liberti L., 2018, OPEN PROBLEMS OPTIMI, P183

[10] On the number of realizations of certain Henneberg graphs arising in protein conformation [J].

Liberti, Leo ;

Masson, Benoit ;

Lee, Jon ;

Lavor, Carlile ;

Mucherino, Antonio .

DISCRETE APPLIED MATHEMATICS, 2014, 165 :213-232

← 1 2 →