8 papers
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
We study the low-degree Steiner forest decomposition. Given a graph and a terminal set , the standard decomposition returns a set of size at…
Minimum Degree Spanning Tree: -Approximation in Near-Linear Time
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established since the early 1990s: Fürer and Raghavachari [FR92] gav…
Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs
Sharareh Alipour, Ermiya Farokhnejad
We study the distributed minimum dominating set problem on graphs of arboricity . Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-loga…
Additive One Approximation for Minimum Degree Spanning Tree: Breaking the Time Barrier
Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang
We consider the ``minimum degree spanning tree'' problem. As input, we receive an undirected, connected graph with nodes and edges, and our task is to find a spa…
Fully Dynamic Euclidean k-Means
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad +3
We consider the Euclidean -means clustering problem in a dynamic setting, where we have to explicitly maintain a solution (a set of centers) subje…
Deterministic -Median Clustering in Near-Optimal Time
Martín Costa, Ermiya Farokhnejad
The metric -median problem is a textbook clustering problem. As input, we are given a metric space of size and an integer , and our task is to find a subset $S \subse…
Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
Sharareh Alipour, Ermiya Farokhnejad, Tobias Mömke
We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the -TSP, where the distances between any two…
Fully Dynamic -Median with Near-Optimal Update Time and Recourse
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad
In metric -clustering, we are given as input a set of points in a general metric space, and we have to pick centers and cluster the input points around these chosen cent…