We study the problem of supervised learning a metric space under discriminative constraints. Given a universe @math and sets @math of similar and dissimilar pairs, we seek to find a mapping @math , into some target metric space @math , such that similar objects are mapped to points at distance at most @math , and dissimilar objects are mapped to points at distance at least @math . More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasipolynomial time (QPTAS). Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest.
 We describe algorithms for the problem of minimum distortion embeddings of finite metric spaces into the real line (or a finite subset of the line). The time complexities of our algorithms are parametrized by the values of the minimum distortion, a#x03B4;, and the spread, a#x0394;, of the point set we are embedding. We consider the problem of finding the minimum distortion bijection between two finite subsets of the Euclidean line. This problem was known to have an exact polynomial time solution when a#x03B4; is below a specific small constant, and hard to approximate within a factor of a#x03B4;1 -- a#x03B5;, when a#x03B4; is polynomially large. Let D be the largest adjacent pair distance, a value potentially much smaller than a#x0394;. Then we provide a a#x03B4;O(a#x03B4;2 log2 D) n O(1) time exact algorithm for this problem, which in particular yields a quasipolynomial running time for constant a#x03B4;, and polynomial D. For the more general problem of embedding any finite metric space (X, dX) into a finite subset of the line, Y, we provide a a#x03B4;O(a#x03B4;2) (mn)O(1) time O(1)-approximation algorithm (where |X|=n and |Y|=m), which runs in polynomial time provided a#x03B4; is a constant and a#x03B4; is polynomial. This in turn allows us to get a a#x03B4;O(a#x03B4;2) (n)O(1) time O(1)-approximation algorithm for embedding (X, dX) into the continuous real line. We consider the problem of embedding general metrics into trees. We give the first non-trivial approximation algorithm for minimizing the multiplicative distortion. Our algorithm produces an embedding with distortion (c log n)O(√log Δ), where c is the optimal distortion, and Δ is the spread of the metric (i.e. the ratio of the diameter over the minimum distance). We give an improved O(1)-approximation algorithm for the case where the input is the shortest path metric over an unweighted graph. Moreover, we show that by composing our approximation algorithm for embedding general metrics into trees, with the approximation algorithm of [BCIS05] for embedding trees into the line, we obtain an improved approximation algorithm for embedding general metrics into the line. We also provide almost tight bounds for the relation between embedding into trees and embedding into spanning subtrees. We show that for any unweighted graph G, the ratio of the distortion required to embed G into a spanning subtree, over the distortion of an optimal tree embedding of G, is at most O(log n). We complement this bound by exhibiting a family of graphs for which the ratio is Ω(log n log log n). Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e. some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data - a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M = 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves an approximation ratio of M+2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the l sub p norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree tree metric under the l spl infin norm. No nontrivial approximation for general l sub p norms was known before. We present a novel LP formulation for this problem and obtain an O((log n log log n) sup 1 p ) approximation using this. Enroute, we obtain an O((log n log log n) sup 1 p ) approximation for the closest ultrametric under the l sub p norm. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings, and may be useful in other contexts. We consider monotone embeddings of a finite metric space into low-dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main interest is in embeddings into Euclidean spaces. We observe that any metric on n points can be embedded into l2n, while (in a sense to be made precise later), for almost every n-point metric space, every monotone map must be into a space of dimension Ω(n) (Lemma 3).It becomes natural, then, to seek explicit constructions of metric spaces that cannot be monotonically embedded into spaces of sublinear dimension. To this end, we employ known results on sphericity of graphs, which suggest one example of such a metric space--that is defined by a complete bipartite graph. We prove that an δn-regular graph of order n, with bounded diameter has sphericity Ω(n (λ2+1)), where λ2 is the second largest eigenvalue of the adjacency matrix of the graph, and 0<δ≤½ is constant (Theorem 4). We also show that while random graphs have linear sphericity, there are quais-random graphs of logarithmic sphericity (Lemma 7).For the above bound to be linear, λ2 must be constant. We show that if the second eigenvalue of an n 2-regular graph is bounded by a constant, then the graph is close to being complete bipartite. Namely, its adjacency matrix differs from that of a complete bipartite graph in only o(n2) entries (Theorem 5). Furthermore, for any 0<δ<½, and λ2, there are only finitely many δn-regular graphs with second eigenvalue at most λ2 (Corollary 4). We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. The (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop several worst-case bounds and approximation algorithms on ordinal embedding. In particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.   We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into ℝ d , where d is fixed (and small). For d = 1, it was known that approximating the minimum distortion with a factor better than roughly n 1 12 is NP-hard. From this result we derive inapproximability with a factor roughly n 1 (22d-10) for every fixed d ≥ 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala), For d > 3, we obtain a stronger inapproximability result by a different reduction: assuming P≠NP, no polynomial-time algorithm can distinguish between spaces embeddable in ℝ d with constant distortion from spaces requiring distortion at least n c d , for a constant c > 0. The exponent c d has the correct order of magnitude, since every n-point metric space can be embedded in ℝ d with distortion O(n 2 d log 3 2 n) and such an embedding can be constructed in polynomial time by random projection. For d = 2, we give an example of a metric space that requires a large distortion for embedding in ℝ 2 , while all not too large subspaces of it embed almost isometrically.   This paper provides a novel technique for the analysis of randomized algorithms for optimization problems on metric spaces, by relating the randomized performance ratio for any, metric space to the randomized performance ratio for a set of "simple" metric spaces. We define a notion of a set of metric spaces that probabilistically-approximates another metric space. We prove that any metric space can be probabilistically-approximated by hierarchically well-separated trees (HST) with a polylogarithmic distortion. These metric spaces are "simple" as being: (1) tree metrics; (2) natural for applying a divide-and-conquer algorithmic approach. The technique presented is of particular interest in the context of on-line computation. A large number of on-line algorithmic problems, including metrical task systems, server problems, distributed paging, and dynamic storage rearrangement are defined in terms of some metric space. Typically for these problems, there are linear lower bounds on the competitive ratio of deterministic algorithms. Although randomization against an oblivious adversary has the potential of overcoming these high ratios, very little progress has been made in the analysis. We demonstrate the use of our technique by obtaining substantially improved results for two different on-line problems. In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images.