Optimization Online


Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces

Frank Vallentin (f.vallentin***at***cwi.nl)

Abstract: In this paper we give a lower bound for the least distortion embedding of a distance regular graph into Euclidean space. We use the lower bound for finding the least distortion for Hamming graphs, Johnson graphs, and all strongly regular graphs. Our technique involves semidefinite programming and exploiting the algebra structure of the optimization problem so that the question of finding a lower bound of the least distortion is reduced to an analytic question about orthogonal polynomials.

Keywords: finite metric spaces, Euclidean embeddings, distance regular graphs, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming


Download: [Postscript][PDF]

Entry Submitted: 12/12/2006
Entry Accepted: 12/12/2006
Entry Last Modified: 05/24/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society