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