activity
20092026
most citedTight Analysis of a Multiple-Swap Heuristic for Budgeted Red-Blue Median

6 citations · 14 across the 22 of their papers we have counts for

collaborators
Showing 2026 · cs.DSShow all

5 papers · 2 filters

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

-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…

cs.DS2026

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…