| Popis: |
We study two aspects of metric spaces that affect the computational complexity of geometric problems. First, we study directed cut problems and the associated multi-commodity flow-cut gap on different classes of directed graphs. We look at generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise naturally from the shortest-path distances on directed graphs.Random embeddings are arguably one of the most successful geometric tools in the context of algorithm design. We extend this set of tools to the quasimetric case to obtain the following results. We present a t log O(1) n-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut and the Directed Multicut problems on n-vertex graphs of treewidth t, with running time polynomial in both n and t. We also give O(1)-approximation algorithms for the Uniform Directed Non-Bipartite Sparsest-Cut and the Directed Multicut problems on series-parallel digraphs and digraphs of bounded pathwidth. We also show that any n-point quasimetric space supported on a graph of treewidth t admits a random embedding into quasiultrametric spaces with distortion O(t log 2 n), where quasiultrametrics are a natural generalization of ultrametrics. For directed cycles and directed trees we show an embedding into directed ℓ 1 space with constant distortion.The above results are obtained by considering a generalization of random partitions to the quasimetric case, which we refer to as random quasipartitions. Using this definition and a construction of [Chuzhoy and Khanna 2009] we derive a polynomial lower bound on the distortion of random embeddings of general quasimetric spaces into quasiultrametric spaces. We also establish a lower bound for embedding the shortest-path quasimetric of a graph G into graphs that exclude G as a minor. Finally, we show an Ω(n) lower bound for random non-contracting embeddings of directed cycles into directed trees. These lower bounds are used to show that several embedding results from the metric case do not have natural analogues in the quasimetric setting.Next, we study the effect of dimension on the complexity of computational geometry problems. Specifically, we study problems on subsets of Euclidean space of low fractal dimension. There are several well-studied notions of fractal dimension for sets and measures in Euclidean space. We consider a definition of fractal dimension for finite metric spaces which agrees with standard notions used to empirically estimate the fractal dimension of various sets.We define the fractal dimension of some metric space to be the infimum δ>0, such that for any ε>0, for any ball B of radius r≥ 2ε, and for any ε-net N (that is, for any maximal ε-packing), we have |B ∩ N|=O((r/ε)δ).Using this definition we obtain faster algorithms for a plethora of classical problems on sets of low fractal dimension in Euclidean space. Our results apply to exact and fixed-parameter algorithms, approximation schemes, and spanner constructions. Interestingly, the dependence of the performance of these algorithms on the fractal dimension nearly matches the currently best-known dependence on the standard Euclidean dimension. Thus, when the fractal dimension is strictly smaller than the ambient dimension, our results yield improved solutions in all of these settings. Finally, we present nearly matching lower bounds that complement most of these results. |
