Arrow Research search

Author name cluster

Anastasios Sidiropoulos

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers
2 author rows

Possible papers

26

NeurIPS Conference 2025 Conference Paper

Effective Neural Approximations for Geometric Optimization Problems

  • Samantha Chen
  • Oren Ciolli
  • Anastasios Sidiropoulos
  • Yusu Wang

Neural networks offer a promising data-driven approach to tackle computationally challenging optimization problems. In this work, we introduce neural approximation frameworks for a family of geometric "extent measure" problems, including shape-fitting descriptors (e. g. minimum enclosing ball or annulus). Central to our approach is the \textit{alignment} of our neural model with a new variant of the classical $\varepsilon$-kernel technique from computational geometry. In particular, we develop a new relaxed-$\varepsilon$-kernel theory that maintains the approximation guarantees of the classical $\varepsilon$-kernels but with the crucial benefit that it can be easily implemented with \textit{bounded model complexity} (i. e, constant number of parameters) by the simple SumFormer neural network. This leads to a simple neural model to approximate objects such as the directional width of any input point set, and empirically shows excellent out-of-distribution generalization. Many geometric extent measures, such as the minimum enclosing spherical shell, cannot be directly captured by $\varepsilon$-kernels. To this end, we show that an encode-process-decode framework with our kernel approximating NN used as the ``process'' module can approximate such extent measures, again, with bounded model complexity where parameters scale only with the approximation error $\varepsilon$ and not the size of the input set. Empirical results on diverse point‐cloud datasets demonstrate the practical performance of our models.

PDF Details

FOCS Conference 2021 Conference Paper

Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut

  • Ken-ichi Kawarabayashi
  • Anastasios Sidiropoulos

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 classes of undirected graphs. It has been shown by Linial, London and Rabinovich [20] and by Aumann and Rabani [5] that for general n-vertex graphs it is bounded by O(log n) and the Gupta-Newman-Rabinovich-Sinclair conjecture [13] asserts that it is O(1) for any family of graphs that excludes some fixed minor. We show that the multicommodity flow-cut gap on directed planar graphs is O(log 3 n). This is the first sub-polynomial bound for any family of directed graphs of super-constant treewidth. We remark that for general directed graphs, it has been shown by Chuzhoy and Khanna [11] that the gap is Ω(n 1/7 ), even for directed acyclic graphs. As a direct consequence of our result, we also obtain the first polynomial-time polylogarithmic-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut, and the Directed Multicut problems for directed planar graphs, which extends the long-standing result for undirectd planar graphs by Rao [22] (with a slightly weaker bound). At the heart of our result we investigate low-distortion quasimetric embeddings into directed $e$ 1. More precisely, we construct O(log 2 n)-Lipschitz quasipartitions for the shortest-path quasimetric spaces of planar digrap $hs$, which generalize the notion of Lipschitz partitions from the theory of metric embeddings. This construction combines ideas from the theory of bi-Lipschitz embeddings, with tools form data structures on directed planar graphs.

Details

NeurIPS Conference 2021 Conference Paper

NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs

  • Evan McCarty
  • Qi Zhao
  • Anastasios Sidiropoulos
  • Yusu Wang

Recent years have witnessed a surge of approaches to use neural networks to help tackle combinatorial optimization problems, including graph optimization problems. However, theoretical understanding of such approaches remains limited. In this paper, we consider the geometric setting, where graphs are induced by points in a fixed dimensional Euclidean space. We show that several graph optimization problems can be approximated by an algorithm that is polynomial in graph size n via a framework we propose, call the Baker-paradigm. More importantly, a key advantage of the Baker-paradigm is that it decomposes the input problem into (at most linear number of) small sub-problems of fixed sizes (independent of the size of the input). For the family of such fixed-size sub-problems, we can now design neural networks with universal approximation guarantees to solve them. This leads to a mixed algorithmic-ML framework, which we call NN-Baker that has the capacity to approximately solve a family of graph optimization problems (e. g, maximum independent set and minimum vertex cover) in time linear to input graph size, and only polynomial to approximation parameter. We instantiate our NN-Baker by a CNN version and GNN version, and demonstrate the effectiveness and efficiency of our approach via a range of experiments.

PDF Details

NeurIPS Conference 2019 Conference Paper

A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families

  • Brian Axelrod
  • Ilias Diakonikolas
  • Alistair Stewart
  • Anastasios Sidiropoulos
  • Gregory Valiant

We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given $n$ points in $\mathbb{R}^d$ and an accuracy parameter $\eps>0$, runs in time $\poly(n, d, 1/\eps), $ and returns a log-concave distribution which, with high probability, has the property that the likelihood of the $n$ points under the returned distribution is at most an additive $\eps$ less than the maximum likelihood that could be achieved via any log-concave distribution. This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task. Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, ``locally'' possesses key properties of exponential families. This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method. Efficiently approximating the (sub) gradients of the objective function of this optimization problem is quite delicate, and is the main technical challenge in this work.

PDF Details

STOC Conference 2019 Conference Paper

Polylogarithmic approximation for Euler genus on bounded degree graphs

  • Ken-ichi Kawarabayashi
  • Anastasios Sidiropoulos

Computing the Euler genus of a graph is a fundamental problem in algorithmic graph theory. It has been shown to be NP-hard by [Thomassen ’89, Thomassen ’97], even for cubic graphs, and a linear-time fixed-parameter algorithm has been obtained by [Mohar ’99]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of an O (1)-approximation is not ruled out, the currently best-known upper bound is a O ( n 1−α )-approximation, for some universal constant α>0 [Kawarabayashi and Sidiropoulos 2017]. We present an O (log 2.5 n )-approximation polynomial time algorithm for this problem on graphs of bounded degree. Prior to our work, the best known result on graphs of bounded degree was a n Ω(1) -approximation [Chekuri and Sidiropoulos 2013]. As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem and for the minimum vertex planarization problem, on graphs of bounded degree. Specifically, we obtain a polynomial-time O ( 2 log 3.5 n )-approximation algorithm for the minimum vertex planarization problem, on graphs of maximum degree . Moreover we obtain an algorithm which given a graph of crossing number k , computes a drawing with at most k 2 log O (1) n crossings in polynomial time. This also implies a n 1/2 log O (1) n -approximation polynomial time algorithm. The previously best-known result is a polynomial time algorithm that computes a drawing with k 10 log O (1) crossings, which implies a n 9/10 log O (1) n -approximation algorithm [Chuzhoy 2011].

Details

SODA Conference 2017 Conference Paper

Metric embeddings with outliers

  • Anastasios Sidiropoulos
  • Dingkang Wang
  • Yusu Wang 0001

We initiate the study of metric embeddings with outliers. Given some finite metric space we wish to remove a small set of points and to find either an isometric or a low-distortion embedding of the remaining points into some host metric space. This is a natural problem that captures scenarios where a small fraction of points in the input corresponds to noise. We present polynomial-time approximation algorithms for computing outlier embeddings into Euclidean space, trees, and ultrametrics. In the case of isometric embeddings the objective is to minimize the number of outliers, while in the case of non-isometries we have a bi-criteria optimization problem where the goal is to minimize both the number of outliers and the distortion. We complement our approximation algorithms with NP-hardness results for these problems. We conclude with a brief experimental evaluation of our non-isometric outlier embedding on synthetic and real-world data sets.

Details

FOCS Conference 2017 Conference Paper

Polylogarithmic Approximation for Minimum Planarization (Almost)

  • Ken-ichi Kawarabayashi
  • Anastasios Sidiropoulos

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 topological graph theory. We present a log O(1) n-approximation algorithm for this problem on general graphs with running time n O(log n/log log n). We also obtain a O(n ε )-approximation with running time n O(1/ε) for any arbitrarily small constant ε > 0. Prior to our work, no non-trivial algorithm was known for this problem on general graphs, and the best known result even on graphs of bounded degree was a n Ω(1) -approximation [1]. As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem on graphs of bounded degree. Specifically, we obtain O(n 1/2+ε )approximation and n 1/ 2 log O(1) n-approximation algorithms in time n O(1/ε) and n O(log n/log log n) respectively. The previously best-known result was a polynomial-time n 9/10 log O(1) n-approximation algorithm [2]. Our algorithm introduces several new tools including an efficient grid-minor construction for apex graphs, and a new method for computing irrelevant vertices. Analogues of these tools were previously available only for exact algorithms. Our work gives efficient implementations of these ideas in the setting of approximation algorithms, which could be of independent interest.

Details

FOCS Conference 2013 Conference Paper

Approximation Algorithms for Euler Genus and Related Problems

  • Chandra Chekuri
  • Anastasios Sidiropoulos

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(√n)-approximation [3] is known even in bounded degree graphs. In this paper we give a polynomialtime algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g O(1) · log O(1) n. Combined with the upper bound from [3], our result also implies a O(n 1/2-α )-approximation, for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPT O(1) · log O(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [5], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.

Details

FOCS Conference 2013 Conference Paper

Non-positive Curvature and the Planar Embedding Conjecture

  • Anastasios Sidiropoulos

The planar embedding conjecture asserts that any planar metric admits an embedding into L_1 with constant distortion. This is a well-known open problem with important algorithmic implications, and has received a lot of attention over the past two decades. Despite significant efforts, it has been verified only for some very restricted cases, while the general problem remains elusive. In this paper we make progress towards resolving this conjecture. We show that every planar metric of non-positive curvature admits a constant-distortion embedding into L_1. This confirms the planar embedding conjecture for the case of non-positively curved metrics.

Details

SODA Conference 2011 Conference Paper

On Graph Crossing Number and Edge Planarization

  • Julia Chuzhoy
  • Yury Makarychev
  • Anastasios Sidiropoulos

Given an n -vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graph's crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with O(log 2 n ). ( n + OPT) crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Planarization problem on graph G, then we can efficiently find a drawing of G with at most poly( d ) · k · ( k + OPT) crossings, where d is the maximum degree in G. This result implies an O ( n · poly( d ) · log 3/2 n )-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k -apex and bounded-genus graphs.

Details

FOCS Conference 2010 Conference Paper

Optimal Stochastic Planarization

  • Anastasios Sidiropoulos

It has been shown by Indyk and Sidiropoulos 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 improved to O(g 2 ) by Borradaile, Lee and Sidiropoulos. We give an embedding with distortion O(log g), which is asymptotically optimal. Apart from the improved distortion, another advantage of our embedding is that it can be computed in polynomial time. In contrast, the algorithm of requires solving an NP-hard problem. Our result implies in particular a reduction for a large class of geometric optimization problems from instances on genus-p graphs, to corresponding ones on planar graphs, with a O(log g) loss factor in the approximation guarantee.

Details

FOCS Conference 2008 Conference Paper

Inapproximability for Metric Embeddings into R^d

  • Jirí Matousek 0001
  • Anastasios Sidiropoulos

We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into R. d, where d is fixed (and small). For d = 1, it was known that approximating the minimum distortion with a factor better than roughly n 1/12 is NP-hard. From this result we derive inapproximability with factor roughly n 1/(22d-10) for every fixed d ges 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala). For d ges 3, we obtain a stronger inapproximability result by a different reduction: assuming PneNP, no polynomial- time algorithm can distinguish between spaces embeddable in R. d with constant distortion from spaces requiring distortion at least n c/d, for a constant c > 0. The exponent c/d has the correct order of magnitude, since every n-point metric space can be embedded in R d with distortion O(n 2/d log 3/2 n) and such an embedding can be constructed in polynomial time by random projection. For d = 2, we give an example of a metric space that requires a large distortion for embedding in R 2, while all not too large subspaces of it embed almost isometrically.

Details