Explanipedia

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

Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Sushant Sachdeva , et al. · 2025

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 is based on interior point methods (IPMs) an…

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time Open

Gramoz Goranci, P. Kiss, Neel Patel, Martin P. Seybold, Eva Szilagyi , et al. · 2025

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 matc…

Fully Dynamic Algorithms for Transitive Reduction Open

Gramoz Goranci, Ali Momeni, Nikos Parotsidis · 2025

Given a directed graph $G$, a transitive reduction $G^t$ of $G$ (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of $G$ that preserves the reachability relation between every two vertices in $G$. In this paper, we s…

Fully Dynamic Spectral Sparsification of Hypergraphs Open

Gramoz Goranci, Ali Momeni · 2025

Spectral hypergraph sparsification, a natural generalization of the well-studied spectral sparsification notion on graphs, has been the subject of intensive research in recent years. In this work, we consider spectral hypergraph sparsifica…

Incremental Approximate Maximum Flow via Residual Graph Sparsification Open

Gramoz Goranci, Monika Henzinger, Harald Räcke, A. R. Sricharan · 2025

We give an algorithm that, with high probability, maintains a (1-ε)-approximate s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow …

Electrical Flows for Polylogarithmic Competitive Oblivious Routing Open

Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan · 2024

Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-…

Dynamic algorithms for <i>k</i>-center on graphs Open

Emilio Cruciani, Sebastian Förster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos · 2024

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into k sets by choosing k centers such that the maximum distance f…

Fully Dynamic Algorithms for Euclidean Steiner Tree Open

T-H. Hubert Chan, Gramoz Goranci, Shaofeng H. -C. Jiang, Bo Wang, Quan Xue · 2023

The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points $X$ in $\mathbb{R}^d$, possibly using points not in $X$ which are called Steiner points. Even though near-linear ti…

Fast Algorithms for Separable Linear Programs Open

Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, Guanghao Ye · 2023

In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A prominent success story is the method of generalized nested diss…

Dynamic algorithms for k-center on graphs Open

Emilio Cruciani, Sebastian Förster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos · 2023

In this paper we give the first efficient algorithms for the $k$-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into $k$ sets by choosing $k$ centers such that the maximum dist…

Fully Dynamic Exact Edge Connectivity in Sublinear Time Open

Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup , et al. · 2023

Given a simple $n$-vertex, $m$-edge graph $G$ undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G$ in $\tilde{O}(n)$ worst-case update time and $\tilde{O}(m…

Efficient Data Structures for Incremental Exact and Approximate Maximum Flow Open

Gramoz Goranci, Monika Henzinger · 2023

We show an (1+ε)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m^{1/2+o(1)} ε^{-1/2} amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow alg…

Bootstrapping Dynamic Distance Oracles Open

Sebastian Förster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos · 2023

Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic, the first result breaking the O(√n) barrier on the update t…

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

Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng , et al. · 2022

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 is based on interior point methods (IPMs) an…

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing Open

Goran Žužić, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun · 2021

We provide universally-optimal distributed graph algorithms for $(1+\varepsilon)$-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any $n$-nod…

Local Algorithms for Estimating Effective Resistance Open

Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci · 2021

Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and network reliability, among others. In spite of the importance of…

Fully Dynamic <i>k</i>-Center Clustering in Low Dimensional Metrics Open

Gramoz Goranci, Monika Henzinger, Dariusz Leniowski, Christian Schulz, Alexander Svozil · 2021

Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications …

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications Open

Sebastian Forster, Gramoz Goranci, Monika Henzinger · 2021

We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for weighted graphs undergoing edge insertions and deletions. We obtain a trade-off between amortized update time and expected stretch against an oblivious …

Minor Sparsifiers and the Distributed Laplacian Paradigm Open

Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun , et al. · 2020

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 comple…

Faster Graph Embeddings via Coarsening Open

Matthew Fahrbach, Gramoz Goranci, Sushant Sachdeva, Richard Peng, Chi Wang · 2020

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 …

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms Open

Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan · 2020

We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with $n$ vertices undergoing edge insertions and deletions using $n…

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers Open

Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak · 2020

We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, g…

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with\n Applications Open

Sebastian Förster, Gramoz Goranci, Monika Henzinger · 2020

We give the first non-trivial fully dynamic probabilistic tree embedding\nalgorithm for weighted graphs undergoing edge insertions and deletions. We\nobtain a trade-off between amortized update time and expected stretch against\nan oblivio…

Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections Open

Gramoz Goranci · 2019

Graphs naturally appear in several real-world contexts including social networks, the web network, and telecommunication networks. While the analysis and the understanding of graph structures have been a central area of study in algorithm …

Fully Dynamic k-Center Clustering in Doubling Metrics Open

Gramoz Goranci, Monika Henzinger, Dariusz Leniowski, Alexander Svozil · 2019

Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications …

Fully Dynamic Spectral Vertex Sparsifiers and Applications Open

David Durfee, Yu Gao, Gramoz Goranci, Richard Peng · 2019

We study \emph{dynamic} algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals $T$ of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy…

Fully dynamic spectral vertex sparsifiers and applications Open

David Durfee, Yu Gao, Gramoz Goranci, Richard Peng · 2019

We study dynamic algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals T of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy of elect…

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs Open

Gramoz Goranci, Monika Henzinger, Pan Peng · 2018

We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+e…

Fully Dynamic Effective Resistances Open

David Durfee, Yu Gao, Gramoz Goranci, Richard Peng · 2018

In this paper we consider the \emph{fully-dynamic} All-Pairs Effective Resistance problem, where the goal is to maintain effective resistances on a graph $G$ among any pair of query vertices under an intermixed sequence of edge insertions …

Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time Open

Gramoz Goranci, Monika Henzinger, Mikkel Thorup · 2018

We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O (log 3 n log log 2 n ) amortized time per edge insertion and O (1) query time. This result partially answers an open question posed b…

Gramoz Goranci YOU? Author Swipe