Distortion lower bounds for line embeddings

TitleDistortion lower bounds for line embeddings
Publication TypeJournal Articles
Year of Publication2008
AuthorsMathieu C, Papamanthou C
JournalInformation Processing Letters
Pagination175 - 178
Date Published2008/10/31/
ISBN Number0020-0190
Keywordscombinatorial problems, Theory of computation

In this paper, we show how we can derive lower bounds and also compute the exact distortion for the line embeddings of some special metrics, especially trees and graphs with certain structure. Using linear programming to formulate a simpler version of the problem gives an interesting intuition and direction concerning the computation of general lower bounds for distortion into the line. We also show that our lower bounds on special cases of metrics are a lot better than previous lower bounds.

Short TitleInformation Processing Letters