Moses Charikar, Konstantin Makarychev, Yury Makarychev

Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_1. This is a natural mathematical question and is also motivated by the study of relaxations ... more >>>