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 cs.DSShow all

30 papers · 1 filter

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…

cs.DS2025

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding

Zachary Friggstad, Tobias Mömke

In Capacitated Vehicle Routing with Multiple Depots (CVRP-MD) we are given a set of client locations and a set of depots located in a metric space with costs betwe…

cs.DS2024★ 1 cited

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii

Zachary Friggstad, Mahya Jamshidian

In this paper, we present an improved approximation algorithm for three related problems. In the Minimum Sum of Radii clustering problem (MSR), we aim to select balls in a metr…

cs.DS2024

Approximate Minimum Sum Colorings and Maximum -Colorable Subgraphs of Chordal Graphs

Ian DeHaan, Zachary Friggstad

We give a -approximation for the minimum sum coloring problem on chordal graphs, improving over the previous 3.591-approximation by Gandhi et al. [2005]. To do so, we al…

cs.DS2024

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…

cs.DS2024

Approximating Traveling Salesman Problems Using a Bridge Lemma

Martin Böhm, Zachary Friggstad, Tobias Mömke +1

We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes $o_1, \ldots, o_…

cs.DS2023

An -Approximation for Directed Steiner Tree in Planar Graphs

Zachary Friggstad, Ramin Mousavi

We present an -approximation for both the edge-weighted and node-weighted versions of \DST in planar graphs where is the number of terminals. We extend our approach…

cs.DS2021★ 2 cited

Parameterized Approximation Algorithms for -Center Clustering and Variants

Sayan Bandyapadhyay, Zachary Friggstad, Ramin Mousavi

-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approxi…

cs.DS2021

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…

cs.DS2021

Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems

Sina Dezfuli, Zachary Friggstad, Ian Post +1

We consider the rooted prize-collecting walks (PCW) problem, wherein we seek a collection of rooted walks having minimum prize-collecting cost, which is the (total cost of walk…

cs.DS2021

A Constant-Factor Approximation for Quasi-bipartite Directed Steiner Tree on Minor-Free Graphs

Zachary Friggstad, Ramin Mousavi

We give the first constant-factor approximation algorithm for quasi-bipartite instances of Directed Steiner Tree on graphs that exclude fixed minors. In particular, for -minor…

cs.DS2019

Graph Pricing with Limited Supply

Zachary Friggstad, Maryam Mahboub

We study approximation algorithms for graph pricing with vertex capacities yet without the traditional envy-free constraint. Specifically, we have a set of items and a set of c…

cs.DS2019

A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time

Zachary Friggstad, Chaitanya Swamy

We give the first constant-factor approximation for the Directed Latency problem in quasi-polynomial time. Here, the goal is to visit all nodes in an asymmetric metric with a singl…

cs.DS2018★ 1 cited

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…

cs.DS2017

Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing

Zachary Friggstad, Chaitanya Swamy

We develop polynomial-size LP-relaxations for {\em orienteering} and the {\em regret-bounded vehicle routing problem} (\rvrp) and devise suitable LP-rounding algorithms that lead t…

cs.DS2017

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…

cs.DS2017★ 1 cited

Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

Sara Ahmadian, Zachary Friggstad

We pursue a study of the Generalized Demand Matching problem, a common generalization of the -Matching and Knapsack problems. Here, we are given a graph with vertex capacities,…

cs.DS2016

A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs

Zachary Friggstad, Jochen Koenemann, Mohammad Shadravan

We demonstrate that the integrality gap of the natural cut-based LP relaxation for the directed Steiner tree problem is in quasi-bipartite graphs with terminals. Su…

cs.DS2016★ 6 cited

Tight Analysis of a Multiple-Swap Heuristic for Budgeted Red-Blue Median

Zachary Friggstad, Yifeng Zhang

Budgeted Red-Blue Median is a generalization of classic -Median in that there are two sets of facilities, say and , that can be used to serve clients…

cs.DS2016

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…