We study the complexity of geometric problems on spaces of low fractal dimension. It was recently shown by [Sidiropoulos & Sridhar, SoCG 2017] that several problems admit improved solutions when the input is a pointset in Euclidean space with fractal dimension smaller than the ambient dimension. In this paper we prove nearly-matching lower bounds, thus establishing nearly-optimal bounds for various problems as a function of the fractal dimension. More specifically, we show that for any set of @math points in @math -dimensional Euclidean space, of fractal dimension @math , for any @math and @math , any @math -spanner must have treewidth at least @math , matching the previous upper bound. The construction used to prove this lower bound on the treewidth of spanners can also be used to derive lower bounds on the running time of algorithms for various problems, assuming the Exponential Time Hypothesis. We provide two prototypical results of this type. For any @math and any @math we show that: 1) @math -dimensional Euclidean TSP on @math points with fractal dimension at most @math cannot be solved in time @math . The best-known upper bound is @math . 2) The problem of finding @math -pairwise non-intersecting @math -dimensional unit balls axis parallel unit cubes with centers having fractal dimension at most @math cannot be solved in time @math for any computable function @math . The best-known upper bound is @math . The above results nearly match previously known upper bounds from [Sidiropoulos & Sridhar, SoCG 2017], and generalize analogous lower bounds for the case of ambient dimension due to [Marx & Sidiropoulos, SoCG 2014].
There has been a large body of work on determining the effect of dimension on the complexity of various geometric problems @cite_22 @cite_24 @cite_11 @cite_1 @cite_12 @cite_28 @cite_27 @cite_5 @cite_26 @cite_18 . Other notions of dimension that have been considered include low-dimensional negatively curved spaces @cite_7 , growth-restricted metrics @cite_2 , as well as generalizations of doubling dimension to metrics of so-called bounded global growth @cite_6 . In all of the above lines of research the goal is to extend tools and ideas from the Euclidean setting to more general geometries. In contrast, we study restricted classes of Euclidean instances, with the goal of obtaining better bounds than what is possible in the general case.
@cite_18 @cite_26 @cite_22 @cite_7 @cite_28 @cite_1 @cite_6 @cite_24 @cite_27 @cite_2 @cite_5 @cite_12 @cite_11
2036959865 2053578961 1615542443 2075022748
We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation algorithms. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L1.We present some new observations concerning the relation of L1 to dimension, topology, and Euclidean distortion. We show that every n-point subset of L1 embeds into L2 with average distortion O(√log n), yielding the first evidence that the conjectured worst-case bound of O(√log n) is valid. We also address the issue of dimension reduction in Lp for p ∈ (1, 2). We resolve a question left open by M. Charikar and A. Sahai [Dimension reduction in the l1 norm, in: Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science, ACM, 2002, pp. 251-260] concerning the impossibility of dimension reduction with a linear map in the above cases, and we show that a natural variant of the recent example of Brinkman and Charikar [On the impossibility of dimension reduction in l1, in: Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, ACM, 2003, pp. 514-523], cannot be used to prove a lower bound for the non-linear case. This is acomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space. The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2k balls of radius r. This concept for abstract metrics has been proposed as a natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics: Quasi-polynomial time (1+e)-approximation algorithm for various optimization problems such as TSP, k-median and facility location. (1+e)-approximate distance labeling scheme with optimal label length. (1+e)-stretch polylogarithmic storage routing scheme. We prove an extension of McDiarmid's inequality for metric spaces with unbounded diameter. To this end, we introduce the notion of the subgaussian diameter, which is a distribution-dependent refinement of the metric diameter. Our technique provides an alternative approach to that of Kutin and Niyogi's method of weakly difference-bounded functions, and yields nontrivial, dimension-free results in some interesting cases where the former does not. As an application, we give apparently the first generalization bound in the algorithmic stability setting that holds for unbounded loss functions. This yields a novel risk bound for some regularized metric regression algorithms. We give two extensions of the basic concentration result. The first enables one to replace the independence assumption by appropriate strong mixing. The second generalizes the subgaussian technique to other Orlicz norms. We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to Bourgain (1985) and Rao (1999). We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion (O ( _ X n ) , ) where α X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an (O ( ( _ X ) n ) ) distortion embedding, where λ X is the doubling constant of X. Since λ X ≤ n, this result recovers Bourgain’s theorem, but when the metric X is, in a sense, “low-dimensional,” improved bounds are achieved.