From the 1 of 7 linked papers with an AI index.
7 papers
Minimum Degree Spanning Tree: -Approximation in Near-Linear Time
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
The paper presents a near‑linear‑time algorithm that computes a spanning tree whose maximum degree is within a factor (1+ε) of the optimal plus one, improving previous approximatio…
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-log…
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…
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…
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…