6 citations · 14 across the 22 of their papers we have counts for
5 papers · 1 filter
Minimum Sum-of-Radii Clustering with Strong and Weak Oracles
Zachary Friggstad, Mahya Jamshidian, Ali Vakilian
In the minimum sum of radii (MSR) problem, the input is a set of points in a metric space and a parameter , and the goal is to cover the points by at most balls, each ce…
A PTAS for Euclidean Capacitated Vehicle Routing
Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi +2
In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an -node graph with metric edges costs , a depot $r\in…
Facility Location with Customer Incompatibilities
Zachary Friggstad, Pengfei Wu
We study metric facility location with customer incompatibilities, where the clients assigned to each facility must satisfy prescribed independence constraints. We first consider t…
-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering
Zachary Friggstad, Mahya Jamshidian, Ali Vakilian
In the weak-strong distance oracle model of Bateni, Dharangutte, Jayaram and Wang (COLT 2024), a metric on points is accessed through two oracles: a cheap weak oracle t…
Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
Zachary Friggstad, Pengfei Wu
We study \textsc{Capacitated Facility Location}, a fundamental clustering problem, in the setting of uniform opening costs and non-uniform capacities. We give a polynomial-time $(3…