Publications
Copyright note: The copyright of the many of these published papers has been transferred to the respective publisher. Such papers cannot be copied or used for commercial purposes.
Approximation Algorithms:
2020

Z. Friggstad and C. Swamy
A ConstantFactor Approximation for the Directed Latency Problem in QuasiPolynomial Time
To appear in ESA, 2020.
2019
2018

Z. Friggstad, S. Gollapudi, K. Kollias, T. Sarlos, C. Swamy, and A. Tomkins
Orienteering Algorithms for Generating Travel Itineraries
In proceedings of WSDM, 2018.

Z. Friggstad, K. Khodamoradi, M. Rezapour, and M. R. Salavatipour
Approximation Schemes for Clustering with Outliers.
In proceedings of SODA, 2018.

Z. Goldthorpe, J. Cannon, J. Farebrother, Z. Friggstad, and M. Nascimento
Using biconnected components for efficient identification of upstream features in large spatial networks.
In SIGSPATIAL/GIScup, 2018.
Comment: The first three authors were undergraduate students at the time. This paper describes their approach for
addressing the GIScup 2018 contest. They won 3rd place.
2017

Z. Friggstad, A. Golestanian, K. Khodamoradi, C. S. Martin, M. Rahgoshay, M. Rezapour, M. R. Salavatipour, and Y. Zhang
Scheduling Problems over Network of Machines.
In proceedings of APPROX, 2017.

S. Ahmadian and Z. Friggstad
Further Approximations for Demand Matching: Matroid Constraints and MinorClosed Graphs.
In proceedings of ICALP, 2017.

Z. Friggstad and C. Swamy
Compact, ProvablyGood LPs for Orienteering and RegretBounded Vehicle Routing.
In proceedings of IPCO, 2017.
2016

Z. Friggstad, M. Rezapour, and M. R. Salavatipour
Local Search Yields a PTAS for kMeans in Doubling Metrics.
In proceedings of FOCS, 2016.
To appear in a special issue of SICOMP.

Z. Friggstad and Y. Zhang
Tight Analysis of a MultipleSwap Heuristic for Budgeted RedBlue Median.
In proceedings of ICALP, 2016.

Z. Friggstad, J. Konemann, and M. Shadravan
A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasibipartite Graphs.
In proceedings of SWAT, 2016.

Z. Friggstad, M. Rezapour, and M. R. Salavatipour
Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding.
In proceedings of SWAT, 2016.
2015

R. Benkoczi, Z. Friggstad, D. Gaur, and M. Thom
Minimizing Total Sensor Movement for Barrier Coverage by Nonuniform Sensors on a Line.
In proceedings of ALGOSENSORS, 2015.

Z. Friggstad, Z. Gao
On Linear Programming Relaxations for Unsplittable Flow in Trees.
In proceedings of APPROX, 2015.

B. Behsaz, Z. Friggstad, M.R. Salavatipour, and R. Sivakumar
Approximation Algorithms for MinSum kClustering and Balanced kMedian
In proceedings of ICALP, 2015.

Z. Friggstad, M. Rezapour, M. R. Salavatipour, J. A. Soto
LPbased Approximation Algorithms for Facility Location in BuyatBulk Network Design
In proceedings of WADS, 2015.
2014

S. Ahmadian, B. Behsaz, Z. Friggstad, A. Jorati, M.R. Salavatipour, and C. Swamy
Approximation Algorithms for MinimumLoad kFacility Location
In proceedings of APPROX 2014.

Z. Friggstad and C. Swamy
Approximation Algorithms for RegretBounded Vehicle Routing with Applications to DistanceConstrained Vehicle Routing
In proceedings of STOC, 2014.

Z. Friggstad, Y. K. Ko, J. Könemann, A. Louis, M. Shadravan, and M. Tulsiani
Linear Programming Hierarchies Suffice for Directed Steiner Tree
In proceedings of IPCO, 2014.
2013
2012
Earlier

Z. Friggstad, M.R. Salavatipour and Z. Svitkina
Asymmetric Traveling Salesman Path and Directed Latency Problems
SIAM J. Comput, 42(4), 15961619, 2013.
Preliminary version in proceedings of SODA 2010.

N. Bansal, Z. Friggstad, R. Khandekar and M.R. Salavatipour
A Logarithmic Approximation for the Unsplittable Flow on Line Graphs
ACM Transactions on Algorithms, 10(1):1, 2014. Preliminary version in proceedings of SODA 2009.

Z. Friggstad and M.R. Salavatipour
Minimizing Movement in Mobile Facility Location Problems
In proceedings of FOCS 2008.
The full version appears in ACM Transactions on Algorithms, 7(3):28, 2011.

Z. Friggstad and M.R. Salavatipour
Approximability of Packing Disjoint Cycles
In proceedings of ISAAC 2007.
A short note of the result
can be found in Algorithmica, 60:395400, 2011.
Mathematics:
Miscellaneous:

A. Fellah, Z. Friggstad and S. Nourredine
Deterministic Timed AFA: A New Class of Timed Alternating Finite Automata
Journal of Computer Science 3(1):18, 2007

H. Li and Z. Friggstad
An Efficient Architecture for the AES Mix Columns Operation
IEEE International Symposium on Circuits and Systems, 5:46374640, 2005.
Theses:

Z. Friggstad
Approximation Techniques for Unsplittable Flow and Traveling Salesmen Problems
PhD thesis, Department of Computing Science, University of Alberta, Aug 2011.
Supervisor: Mohammad R. Salavatipour

Z. Friggstad
Minimizing Movement in Mobile Facility Location Problems
M.Sc. thesis, Department of Computing Science, University of Alberta, Aug 2007.
Supervisor: Mohammad R. Salavatipour