6 citations · 14 across the 22 of their papers we have counts for
30 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…
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…
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…
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…
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…
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_…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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,…
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…
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…
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…