12 citations · 15 across the 9 of their papers we have counts for
13 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…
Improved Approximations for CVRP with Unsplittable Demands
Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay +1
In this paper, we present improved approximation algorithms for the (unsplittable) Capacitated Vehicle Routing Problem (CVRP) in general metrics. In CVRP, introduced by Dantzig and…
Hierarchical Clustering: New Bounds and Objective
Mirmahdi Rahgoshay, Mohammad R. Salavatipour
Hierarchical Clustering has been studied and used extensively as a method for analysis of data. More recently, Dasgupta [2016] defined a precise objective function. Given a set of…
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
Aditya Jayaprakash, Mohammad R. Salavatipour
In this paper, we present Approximation Schemes for Capacitated Vehicle Routing Problem (CVRP) on several classes of graphs. In CVRP, introduced by Dantzig and Ramser (1959), we ar…
Approximations for Throughput Maximization
Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, Mohammad R. Salavatipour
In this paper we study the classical problem of throughput maximization. In this problem we have a collection of jobs, each having a release time , deadline , and…
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…
Approximation Schemes for Clustering with Outliers
Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour +1
Clustering problems are well-studied in a variety of fields such as data science, operations research, and computer science. Such problems include variants of centre location probl…
Local Search Yields a PTAS for k-Means in Doubling Metrics
Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour
The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly -means: given a set of data points and a parameter , select…
How to Walk Your Dog in the Mountains with No Magic Leash
Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour +1
We describe a -approximation algorithm for computing the homotopic \Frechet distance between two polygonal curves that lie on the boundary of a triangulated topological…
Asymmetric Traveling Salesman Path and Directed Latency Problems
Zachary Friggstad, Mohammad R. Salavatipour, Zoya Svitkina
We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified node…
A Weakly-Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
Imran A. Pirwani, Mohammad R. Salavatipour
We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor ap…