کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428738 686904 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distortion lower bounds for line embeddings
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Distortion lower bounds for line embeddings
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 108, Issue 4, 31 October 2008, Pages 175-178