TY - JOUR T1 - Distortion lower bounds for line embeddings JF - Information Processing Letters Y1 - 2008 A1 - Mathieu, Claire A1 - Charalampos Papamanthou KW - combinatorial problems KW - Theory of computation AB - 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. VL - 108 SN - 0020-0190 UR - http://www.sciencedirect.com/science/article/pii/S0020019008001464 CP - 4 J1 - Information Processing Letters ER -