Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
Thesis.pdf (1.56 MB)
ETD Abstract Container
Abstract Header
On the effect of asymmetry and dimension on computational geometric problems
Author Info
Sridhar, Vijay, Sridhar
ORCID® Identifier
http://orcid.org/0000-0001-9170-7914
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304
Abstract Details
Year and Degree
2018, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Abstract
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.
Committee
Anastasios Sidiropoulos (Advisor)
Yusu Wang (Advisor)
Facundo Mémoli (Committee Member)
Pages
136 p.
Subject Headings
Computer Science
Keywords
Metric-Embeddings
;
Quasimetrics
;
Random-Embeddings
;
Treewidth
;
Directed Sparsest-Cut
;
Directed Multi-Cut
;
Fractal-Dimension
;
Exact-Algorithms
;
Fixed-Parameter-Tractability
;
Approximation- Schemes
;
Spanners
;
Lower-Bounds
;
Exponential-Time-Hypothesis
;
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
osu1531362300593304
Download Count:
249
Copyright Info
© 2018, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.