11 citations · 20 across the 11 of their papers we have counts for
7 papers · 1 filter
Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov +2
We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric . Computing such an embedding (exactly…
Fractal dimension and lower bounds for geometric problems
Anastasios Sidiropoulos, Kritika Singhal, Vijay Sridhar
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…
Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
Timothy Carpenter, Ario Salmasi, Anastasios Sidiropoulos
The problem of routing in graphs using node-disjoint paths has received a lot of attention and a polylogarithmic approximation algorithm with constant congestion is known for undir…
On constant multi-commodity flow-cut gaps for directed minor-free graphs
Ario Salmasi, Anastasios Sidiropoulos, Vijay Sridhar
The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide \& conquer algorithms, and has been extensively studied for various class…
Polylogarithmic approximation for minimum planarization (almost)
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
In the minimum planarization problem, given some -vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a funda…
Temporal Hierarchical Clustering
Tamal K. Dey, Alfred Rossi, Anastasios Sidiropoulos
We study hierarchical clusterings of metric spaces that change over time. This is a natural geometric primitive for the analysis of dynamic data sets. Specifically, we introduce an…