We study online embeddings of metric spaces into Euclidean spaces of a constant dimension d > 1, against an adaptive adversary. While the case of d = 1 is well understood, for higher dimensions little is known. In particular, even for d = 2 it remains unknown whether the worst-case distortion grows exponentially with the number of exposed points, as it does in the case for the line, or whether it is polynomial, as in the case for unbounded d. Our first result is about fixed solid graphs, i.e., K₅, whose edges are solid intervals, equipped with the shortest-path metric. We show that if the input points arrive from such a metric space, they can indeed be online-embedded into ℝ² with a polynomial distortion. This refutes the previously believed conjecture that the topological non-embeddability of K₅ into the plane could be exploited for establishing exponential lower bounds. The second results is about online embeddings of tree metrics of a certain type, including, e.g., ultrametrics and HST’s. Somewhat surprisingly, we show that for metrics from this class the worst-case online embedding into ℝ^d is not much worse that the offline embedding, both being n^Θ(1/d), and this holds even when d = Θ(log n). This is in a stark contrast to the more common situation where the online-offline gap is typically huge, and even exponential. This result allows us to transfer results about probabilistic embeddings of metrics into HST’s to low-dimensional Euclidean spaces, in an almost optimal possible manner.

We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the 2-dimensional plane. Among other results, we give an $O(\sqrt{n})$-approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved $\tilde{O}(n^{1/3})$ approximation for the case of metrics induced by unweighted trees.

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f : {1,…, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i1 < i2 < · · · < ik, such that f (ix) > f (iy) whenever π(χ) > π(y). If f does not contain π, we say f is π-free. For example, for π = (2,1), the property of being π-free is equivalent to being non-decreasing, i.e. monotone. The property of being (k,k — 1,…, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidden) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i.e., (k,k - 1,…, 1) and (1, 2,…, k), we design non-adaptive one-sided error ε-tests of (∊−1 log n)O(k2) query complexity. For non-monotone patterns, we show that for any size-k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ/η) queries. This general lower bound can be further strengthened for specific non-monotone k-length patterns to Ω(n1–2/(k+1)). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e−1/kn1–1/k) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E.g., for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊−1 logn)O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

Let $\mathcal{F}$ be a set system over an underlying finite set $X$, and let $\mu$ be a nonnegative measure over $X$; i.e., for every $S \subseteq X$, $\mu(S)=\sum_{x\in S} \mu(x)$. A measure $\mu^*$ on $X$ is called a multiplicative ${\lambda}$-approximation of $\mu$ on $(\mathcal{F},X)$ if for every $S\in \mathcal{F}$ it holds that $a\mu(S) \leq \mu^*(S) \leq b \mu(S)$, and $b/a = \lambda \geq 1$. The central question raised and partially answered in the present paper is about the existence of meaningful structural properties of $\mathcal{F}$ implying that for any $\mu$ on $X$ there exists an ${{1+\epsilon} \over {1-\epsilon}}$-approximation $\mu^*$ supported on a small subset of $X$. It turns out that the parameter that governs the support size of a multiplicative approximation is the triangular rank of $\mathcal{F}$, ${\rm trk}(\mathcal{F})$. It is defined as the maximal length of a sequence of sets $\{S_i\}_{i=1}^t $ in $\mathcal{F}$ such that for all $1

Let F be a set system over an underlying finite set X, and let μ be a nonnegative measure over X. I.e., for every S ⊆ X, μ(S) = σx ∊ S μ(x). A measure μ* on X is called a multiplicative λ-approximation of μ on (F, X) if for every S ∊ F it holds that aμ(S) ≤ μ*(S) ≤ bμ(S), and b/a = λ ≥ 1. The central question raised and partially answered in the present paper is about the existence of meaningful structural properties of F implying that for any μ on X there exists an -approximation μ* supported on a small subset of X. It turns out that the parameter that governs the support size of a multiplicative approximation is the triangular rank of F, trk(F). It is defined as the maximal length of a sequence of sets {Si}ti = 1 in F such that for all 1 < i ≤ t, Si ⊊ ∪j < i Sj. We show that for any μ on X and 0 < ∊ < 1, there is measure μ* that -approximates μ on (X, F), and has support of size O(trk(F)2 log(trk(F))/poly(∊)). We also present two alternative constructions which in some cases improve upon this bound. Conversely, we show that for any 0 ≤ ∊ < 1 there exists a μ on X that cannot be -approximated on (F, X) by any μ* with support of size < trk(F). For special families F this bound can be improved to Ω(trk(F)/∊). As an application we show a new dimension-reduction result for ℓ1 metrics: Any ℓ1-metric on n points can be (efficiently) embedded with -distortion into ℝO(n/∊2) equipped with the ℓ1 norm. This improves over the best previously known bound of O(n log n/poly(∊)) on dimension, due to Schechtman. We obtain also some new results on efficient sampling of Euclidean volumes. In order to make the general framework applicable to this setting, we develop the basic theory of finite volumes, analogous to the theory of finite metrics, and get results of independent interest in this direction. To do so, we use basic combinatorial/topological facts about simplicial complexes, and study the naturally arising questions.

Motivated by applications in combinatorial optimization, we study the extent to which the global properties of a metric space, and especially its embeddability into $\ell_1$ with low distortion, are determined by the properties of its small subspaces. We establish both upper and lower bounds on the distortion of embedding locally constrained metrics into various target spaces. Other aspects of locally constrained metrics are studied as well, in particular, how far are those metrics from general metrics.

We study various computational aspects of the problem of determining whether, given a (fixed) permutation $\pi$ on k elements and an input permutation $\sigma$ on $n > k$ elements, $\pi$ can be embedded in $\sigma$ in an order-preserving manner. Formally, the goal is to determine whether there exists a strictly increasing function f from $[1,k]$ to $[1,n]$ which is order preserving, i.e., f satisfies $\sigma(f(i)) > \sigma(f(j))$ whenever $\pi(i) > \pi(j)$. We call this decision problem the subpattern problem. The study falls into two parts. In the first part we develop and analyze an algorithmic paradigm for this problem. We introduce two naturally defined (related) permutation-complexity measures $C(\pi)$ and a somewhat finer $C^{\bf T}(\pi)$, and, we show that our algorithms run in time $O(n^{1 + C(\pi)})$ and $O(n^{2 \cdot C^{\bf T}(\pi)})$, respectively; i.e., the hardness of the problem crucially depends on the structure of $\pi$, as measured by $C(\pi)$ or by $C^{\bf T}(\pi)$. In the second part of the paper we study the above complexity measures. In particular, we show that in the general case, $C(\pi) \leq 0.47k + o(k)$. Thus, the time complexity of the subpattern problem is at most $O(n^{0.47k + o(k)})$, improving over the trivial $O(n^k)$. Unfortunately, it turns out that for most permutations $C^{\bf T}(\pi) = \Omega(k)$, and thus, in general, the upper bound on the running time cannot be significantly improved using this approach. Yet, for many natural classes of permutations the complexity of $C(\pi)$ is sublinear in k. To demonstrate this, we study two interesting classes of “linear” permutations and show that their complexity is $C(\pi) = O(\sqrt{k})$. In addition, we study some structural properties of the complexity measures, show that $C^{\bf T}(\pi) \leq C(\pi) \leq O(\log k) \cdot C^{\bf T}(\pi)$, and relate $C(\pi)$ and $C^{\bf T}(\pi)$ to the pathwidth and the treewidth of a certain graph $G_\pi$ defined by the permutation $\pi$.

We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion and hence also embedded into $\ell_1$ with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs and include the family of weighted $k\times n$ planar grids. This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outerplanar graphs, thus extending a theorem of Okamura and Seymour [J. Combin. Theory Ser. B, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of Gupta et al. [Combinatorica, 24(2004), pp. 233-269] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We conjecture that these embeddings for k-outerplanar graphs may serve as building blocks for $\ell_1$ embeddings of more general metrics.

We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture, and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. We establish close mutual relations between the MinCut- MaxFlow gap in a uniform-demand multicommodity flow, and the average distortion of embedding the suitable (dual) metric into l1. These relations are exploited to show that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) graphs embed into l1 with constant average distortion. The main result of the paper claims that this remains true even if l1 is replaced with the line. This result is further sharpened for graphs of a bounded treewidth.

(MATH) We exhibit a simple infinite family of series-parallel graphs that cannot be metrically embedded into Euclidean space with distortion smaller than $\Omega(\sqrt\log n\,)$. This matches Rao's general upper bound for metric embedding of planar graphs into Euclidean space, [14], thus resolving the question of how well do planar metrics embed in Euclidean spaces.

Motivated by many recent algorithmic applications, the paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred where the graph is embedded into l/sub 1/ space. The main results are: 1. Explicit constant-distortion embeddings of all series parallel graphs, and all graphs with bounded Euler number. These are thus the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, we obtain algorithms to approximate the sparsest cut in such graphs to within a constant factor. 2) A constant-distortion embedding of outerplanar graphs into the restricted class of l/sub 1/-metrics known as "dominating tree metrics". We also show a lower bound of /spl Omega/(log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low tree width, and excludes the possibility of using them to explore the finer structure of l/sub 1/-embeddability.

Article Free Access Share on A computational view of population genetics Authors: Yuval Rabani Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, Canada Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, CanadaView Profile , Yuri Rabinovich Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, Canada Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4, CanadaView Profile , Alistair Sinclair Computer Science Division, University of California, Berkeley, CA Computer Science Division, University of California, Berkeley, CAView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 83–92https://doi.org/10.1145/225058.225088Online:29 May 1995Publication History 19citation457DownloadsMetricsTotal Citations19Total Downloads457Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We explore some implications of viewing graphs as geometric 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 the metric of the (possibly weighted) graph. Given a graph G 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 small distortion, i.e., make sure that distances between vertices in G closely match the distances between their geometric images. We develop efficient algorithms for embedding graphs low-dimensionally with a small distortion.>

The paper promotes the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. The authors identify the class of symmetric quadratic systems. Such systems have been widely used to model phenomena in the natural sciences, and also provide an appropriate framework for the study of genetic algorithms in combinatorial optimisation. They prove several fundamental general properties of these systems, notably that every trajectory converges to a fixed point. They go on to give a detailed analysis of a quadratic system defined in a natural way on probability distributions over the set of matchings in a graph. In particular, they prove that convergence to the limit requires only polynomial time when the graph is a tree. This result demonstrates that such systems, though nonlinear, are amenable to quantitative analysis.>