Research
Research
Research
Research
18+ open-access research outputs.
Kawarabayashi and Sidiropoulos [KS22] obtained an $O(\log^2 n)$-approximation algorithm for Multicut in planar digraphs via a natural LP relaxation, which also establishes a corresponding upper bound …
Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in $\mathbb{R}^d$ ($d \geq 1$), or equivalently, distanc…
Max-Cut is a fundamental problem that has been studied extensively in various settings. We design an algorithm for Euclidean Max-Cut, where the input is a set of points in $\mathbb{R}^d$, in the model…
In the discrete $k$-center problem, we are given a metric space $(P,\texttt{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq P$ of $k$ centers which minimizes the maximum distance of …
In the F-minor-free deletion problem we want to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family F. The Vertex planarization problem is a special c…
It was conjectured by Gupta et al. [Combinatorica04] that every planar graph can be embedded into $\ell_1$ with constant distortion. However, given an $n$-vertex weighted planar graph, the best upper …
The relationship between the sparsest cut and the maximum concurrent multi-flow in graphs has been studied extensively. For general graphs with $k$ terminal pairs, the flow-cut gap is $O(\log k)$, and…
Spanners for low dimensional spaces (e.g. Euclidean space of constant dimension, or doubling metrics) are well understood. This lies in contrast to the situation in high dimensional spaces, where exce…
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 i…
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep …
In the minimum planarization problem, given some $n$-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a fundamental problem in to…
We study the problem of embedding shortest-path metrics of weighted graphs into $\ell_p$ spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths.…
In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability of ATSP on topologic…
In this paper, we prove that any non-positively curved 2-dimensional surface (alias, Busemann surface) is isometrically embeddable into $L_1$. As a corollary, we obtain that all planar graphs which ar…
It has been recently shown that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs, with distortion Olog (g+1)) [Sidiropoulos, FOCS 2010]. This embedding can …
It has been shown by Indyk and Sidiropoulos [IS07] that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs with distortion 2^O(g). This bound was later improv…
Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g-1$ with constant distortion. Viewing a graph of genus $g$ as embe…
In multi-input-multi-output (MIMO) detection, semidefinite relaxation (SDR) has been shown to be an efficient high-performance approach. Developed initially for BPSK and QPSK, SDR has been found to be…
Free open-access publishing with Google Scholar indexing.
Submission Guide →