Arrow Research search

Author name cluster

Gramoz Goranci

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.

16 papers
2 author rows

Possible papers

16

NeurIPS Conference 2025 Conference Paper

Fully Dynamic Algorithms for Chamfer Distance

  • Gramoz Goranci
  • Shaofeng Jiang
  • Peter Kiss
  • Eva Szilagyi
  • Qiaoyuan Yang

We study the problem of computing Chamfer distance in the fully dynamic setting, where two sets of points $A, B \subset \mathbb{R}^{d}$, each of size up to $n$, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to $dist_{\mathrm{CH}}(A, B) = \sum_{a \in A} \min_{b \in B} dist(a, b)$, where $dist$ is a distance measure. Chamfer distance is a widely used dissimilarity metric for point clouds, with many practical applications that require repeated evaluation on dynamically changing datasets, e. g. , when used as a loss function in machine learning. In this paper, we present the first dynamic algorithm for maintaining an approximation of the Chamfer distance under the $\ell_p$ norm for $p \in$ {$1, 2$}. Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain $(1+\epsilon)$-approximation in $\tilde{O}(\epsilon^{-d})$ update time and $O(1/\epsilon)$-approximation in $\tilde{O}(d n^{\epsilon^2} \epsilon^{-4})$ update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.

PDF Details

ICML Conference 2025 Conference Paper

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

  • Gramoz Goranci
  • Peter Kiss
  • Neel Patel
  • Martin P. Seybold
  • Eva Szilagyi
  • Da Wei Zheng

We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.

Details

ICML Conference 2024 Conference Paper

Dynamic Facility Location in High Dimensional Euclidean Spaces

  • Sayan Bhattacharya
  • Gramoz Goranci
  • Shaofeng H. -C. Jiang
  • Yi Qian
  • Yubo Zhang

We study the facility location problem in the dynamic setting, where the goal is to efficiently process an intermixed sequence of point insertions and deletions while maintaining a high quality and stable solution. Although the problem has been studied in the context of general metrics and low-dimensional spaces, much remains unknown concerning dynamic facility location in high dimensional spaces. In this work, we present the first fully dynamic algorithm for facility location in high-dimensional spaces $\mathbb{R}^{d}$. For any $c \geq 1$, our algorithm achieves $O(c)$-approximation, supports point updates in $\tilde{O}(\mathrm{poly}(d)n^{1/c + o(1)})$ amortized time and incurs $O(1)$ amortized recourse. More generally, our result shows that despite the linear-time lower bound on the update time for general metrics, it is possible to achieve sub-linear update times for metric spaces that admit dynamic nearest neighbour oracles. Experiments on real datasets confirm that our algorithm achieves high-quality solutions with low running time, and incurs minimal recourse.

Details

FOCS Conference 2024 Conference Paper

Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs

  • Arnold Filtser
  • Gramoz Goranci
  • Neel Patel
  • Maximilian Probst Gutenberg

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an $n-\mathbf{vertex}$ planar graph $G=(V, E)$ undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a $(1+\epsilon)-\mathbf{approximate}$ dynamic algorithm that supports edge updates and distance queries in $n^{o(1)}$ time, for any $1/\mathbf{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of $\tilde{O}(\sqrt{n})$ on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a $\Omega(\sqrt{n})$ conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].

Details

SODA Conference 2022 Conference Paper

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

  • Sally Dong
  • Yu Gao 0001
  • Gramoz Goranci
  • Yin Tat Lee
  • Richard Peng
  • Sushant Sachdeva
  • Guanghao Ye

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem was based on interior point methods (IPMs) and worked for general sparse graphs in O ( n 1. 5 poly(log n )) time [Daitch-Spielman, STOC'08]. Intuitively, Ω( n 1. 5 ) is a natural runtime barrier for IPM based methods, since they require iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested-dissection [Lipton-Rose-Tarjan, JSTOR'79] and approximate Schur complements [Kyng-Sachdeva, FOCS'16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly update time, resulting in a total running time of O(n · poly(log n )). Our results immediately extend to all families of separable graphs.

Details

SODA Conference 2022 Conference Paper

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ 1 -Oblivious Routing

  • Goran Zuzic
  • Gramoz Goranci
  • Mingquan Ye
  • Bernhard Haeupler
  • Xiaorui Sun

We provide universally-optimal distributed graph algorithms for (1+ ∊ )-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any n -node network G, our algorithm completes in T · n o (1) rounds whenever a T -round algorithm exists for G. This includes D · n o (1) -round algorithms for any planar or excluded-minor network. Our algorithms never require more than rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient n o (1) -competitive linear ℓ 1 -oblivious routing operator that does not require the use of ℓ 1 -embeddings. Our construction is simple, solely based on low-diameter decompositions, and—in contrast to all known constructions—directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.

Details

SODA Conference 2021 Conference Paper

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications

  • Sebastian Forster
  • Gramoz Goranci
  • Monika Henzinger

We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for a weighted, undirected graph G with n nodes and at most m edges undergoing edge insertions and deletions. The goal in this problem is to maintain a tree containing all nodes of G with a randomized algorithm such that for every edge ( u, v ) of G the expected length of the path from u to v in the tree exceeds the weight of the edge ( u, v ) only by a small multiplicative factor, called the stretch of the embedding. In this paper, we obtain a trade-off between amortized update time and expected stretch against an oblivious adversary. At the two extremes of this trade-off, we can maintain a tree of expected stretch O (log 4 n ) with update time m 1/2+ o (1) or a tree of expected stretch n o (1) with update time n o (1) (for edge weights polynomial in n ). A guarantee of the latter type has so far only been known for maintaining tree embeddings with average (instead of expected) stretch [Chechik/Zhang, SODA '20]. Our main result has direct implications to fully dynamic approximate distance oracles and fully dynamic buy-at-bulk network design as our trade-off from above carries over to these two problems with minor overheads. For dynamic distance oracles, our result is the first to break the update-time barrier. For buy-at-bulk network design, a problem which also in the static setting heavily relies on probabilistic tree embeddings, we give the first non-trivial dynamic algorithm. As probabilistic tree embeddings are an important tool in static approximation algorithms, we expect our result to have further applications in dynamic approximation algorithms. From a technical perspective, we obtain our main result by first designing a decremental (i. e. , deletionsonly) algorithm for probabilistic low-diameter decompositions via a careful combination of Bartal's ball-growing approach [FOCS ‘96] with the pruning framework of Chechik and Zhang [SODA ‘20]. Such a low-diameter decomposition is the heart of Bartal's seminal tree embedding construction and we show how to adapt it to the decremental setting. We then extend this to a fully dynamic algorithm by significantly enriching a well-known “decremental to fully dynamic” reduction with a new bootstrapping idea to recursively employ a fully dynamic algorithm instead of a static one in this reduction. By additionally exploiting certain properties of our tree embedding, this bootstrapping scheme can be made highly efficient.

Details

FOCS Conference 2021 Conference Paper

Minor Sparsifiers and the Distributed Laplacian Paradigm

  • Sebastian Forster
  • Gramoz Goranci
  • Yang P. Liu
  • Richard Peng
  • Xiaorui Sun
  • Mingquan Ye

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of $\widetilde{\Omega}(\sqrt{n}+D)$, where $n$ is the number of nodes in the network and $D$ is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.

Details

FOCS Conference 2020 Conference Paper

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

  • Li Chen 0028
  • Gramoz Goranci
  • Monika Henzinger
  • Richard Peng
  • Thatchaphol Saranurak

We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $\tilde{O}(n^{2/3})$ 1 1 The $\tilde{O}(\cdot)$ notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and $\tilde{O}(m^{3/4})$ time against an adaptive adversary. (2)An incremental data structure that maintains $O(1)$ - approximate shortest path in $n^{o(1)}$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $\tilde{O}(n^{2/3 +o(1)})$ amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an ( $1+\epsilon$ ) factor in $\tilde{O}(n^{2/3+o(1)}\epsilon^{-O(1)})$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as $j$ -trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$ -approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https: //arxiv. org/pdf/2005. 02368. pdf for the full version of this paper.

Details

ICML Conference 2020 Conference Paper

Faster Graph Embeddings via Coarsening

  • Matthew Fahrbach
  • Gramoz Goranci
  • Richard Peng
  • Sushant Sachdeva
  • Chi Wang 0001

Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for large-scale graphs is prohibitively inefficient even if we are interested only in a small subset of relevant vertices. To address this, we present an efficient graph coarsening approach, based on Schur complements, for computing the embedding of the relevant vertices. We prove that these embeddings are preserved exactly by the Schur complement graph that is obtained via Gaussian elimination on the non-relevant vertices. As computing Schur complements is expensive, we give a nearly-linear time algorithm that generates a coarsened graph on the relevant vertices that provably matches the Schur complement in expectation in each iteration. Our experiments involving prediction tasks on graphs demonstrate that computing embeddings on the coarsened graph, rather than the entire graph, leads to significant time savings without sacrificing accuracy.

Details