4 papers
A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
Benyamin Ghaseminia, Mohammad R. Salavatipour
We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane () and present a Polynomial-Time Approximation Scheme (PTAS) when the ne…
A QPTAS for Facility Location on Unit Disk graphs
Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour +1
We study the classic \textsc{(Uncapacitated) Facility Location} problem on Unit Disk Graphs (UDGs). For a given point set in the plane, the unit disk graph UDG(P) on has ve…
Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
Kinter Ren, Mohammad R. Salavatipour
In this paper we look at -stroll, point-to-point orienteering, as well as the deadline TSP problem on graphs with bounded doubling dimension and bounded treewidth and present ap…
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
Zachary Friggstad, Kamyar Khodamoradi, Mohammad R. Salavatipour
We investigate the complexity of solving stable or perturbation-resilient instances of -Means and -Median clustering in fixed dimension Euclidean metrics (more generally doub…