3 citations · 11 across the 14 of their papers we have counts for
5 papers · 1 filter
Semi-Streaming Estimation of the Held--Karp Bound and Graph-Metric TSP Cost
Sharareh Alipour
The Held--Karp bound is a linear-programming lower bound for the metric traveling salesperson problem (TSP). We approximate this bound in the multi-pass insertion-only streaming mo…
Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP
Sharareh Alipour, Ali Nowzari
We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, -TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm…
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…
Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
Sharareh Alipour
Many multiagent tasks -- such as reviewer assignment, coalition formation, or fair resource allocation -- require selecting a group of agents such that collaboration remains effect…
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…