Skip to Main Content
 

Global Search Box

 
 
 
 

Files

ETD Abstract Container

Abstract Header

On the effect of asymmetry and dimension on computational geometric problems

Sridhar, Vijay, Sridhar

Abstract Details

2018, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
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.
Anastasios Sidiropoulos (Advisor)
Yusu Wang (Advisor)
Facundo Mémoli (Committee Member)
136 p.

Recommended Citations

Citations

  • Sridhar, Sridhar, V. (2018). On the effect of asymmetry and dimension on computational geometric problems [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304

    APA Style (7th edition)

  • Sridhar, Sridhar, Vijay. On the effect of asymmetry and dimension on computational geometric problems. 2018. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304.

    MLA Style (8th edition)

  • Sridhar, Sridhar, Vijay. "On the effect of asymmetry and dimension on computational geometric problems." Doctoral dissertation, Ohio State University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304

    Chicago Manual of Style (17th edition)