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:

2022

• S. Dezfuli, Z. Friggstad, I. Post and C. Swamy
  Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems
  In proceedings of IPCO, 2022.


• Z. Friggstad, R. Mousavi, M. Rahgoshay, and M. R. Salavatipour
  Improved Approximations for CVRP with Unsplittable Demands
  In proceedings of IPCO, 2022.


• S. Bandyapadhyay, Z. Friggstad, and R. Mousavi
  Parameterized Approximation Algorithms for K-center Clustering and Variants
  In proceedings of AIII, 2022. Full version forthcoming.

2021

• Z. Friggstad and C. Swamy
  Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime
  In proceedings of ICALP, 2021
  Full version in Journal of Computer and System Sciences, 126: 44-58, 2002.


• Z. Friggstad and M. Mahboub
  Graph Pricing With Limited Supply
  In proceedings of WADS, 2021.


• Z. Friggstad and R. Mousavi
  Fair Correlation Clustering with Global and Local Guarantees
  In proceedings of WADS, 2021.

2020

• Z. Friggstad and C. Swamy
  A Constant-Factor Approximation for the Directed Latency Problem in Quasi-Polynomial Time
  In proceedings of ESA, 2020.

2019

• Z. Friggstad, K. Khodamoradi, and M. R. Salavatipour
  Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
  In proceedings of SODA, 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 submission to 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 Minor-Closed Graphs.
  In proceedings of ICALP, 2017.


• Z. Friggstad and C. Swamy
  Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing.
  In proceedings of IPCO, 2017.

2016

• Z. Friggstad, M. Rezapour, and M. R. Salavatipour
  Local Search Yields a PTAS for k-Means 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 Multiple-Swap Heuristic for Budgeted Red-Blue Median.
  In proceedings of ICALP, 2016.


• Z. Friggstad, J. Konemann, and M. Shadravan
  A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite 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 Non-uniform 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 Min-Sum k-Clustering and Balanced k-Median
  In proceedings of ICALP, 2015.


• Z. Friggstad, M. Rezapour, M. R. Salavatipour, J. A. Soto
  LP-based Approximation Algorithms for Facility Location in Buy-at-Bulk 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 Minimum-Load k-Facility Location
  In proceedings of APPROX 2014.


• Z. Friggstad and C. Swamy
  Approximation Algorithms for Regret-Bounded Vehicle Routing with Applications to Distance-Constrained 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

• Z. Friggstad, A. Gupta, and M. Singh
  An Improved Integrality Gap for Asymmetric TSP Paths
  In proceedings of IPCO 2013.
  Journal version in Mathematics of Operations Research.
  


• S. Ahmadian, Z. Friggstad, and C. Swamy
  Local-Search Based Approximation Algorithms for Mobile Facility Location Problems
  In proceedings of SODA 2013.
  Full version with single swap analysis is available on arXiv, manuscript number 1301.4478.


• E. Chlamtac, Z. Friggstad, and K. Georgiou
  Lift-and-Project Methods for Set Cover and Knapsack
  In proceedings of WADS 2013.
  Available on arXiv (with a different title), manuscript number 1204.5489.


• Z. Friggstad
  Multiple Traveling Salesmen in Asymmetric Metrics
  In proceedings of APPROX 2013.
  Available on arXiv, manuscript number 1112.2930.

2012

• J. Cheriyan, Z. Friggstad, and Z. Gao
  Approximating Minimum-Cost Connected T-Joins
  Algorithmica 72(1):126-147, 2015. Preliminary version in proceedings of APPROX 2012.
  

Earlier

• Z. Friggstad, M.R. Salavatipour and Z. Svitkina
  Asymmetric Traveling Salesman Path and Directed Latency Problems
  SIAM J. Comput, 42(4), 1596--1619, 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:395-400, 2011.

---

Mathematics:

• A. Akbary and Z. Friggstad
  Superabundant Numbers and the Riemann Hypothesis
  The American Mathematical Monthly, 116(3):273-275, 2009.


• A. Akbary, Z. Friggstad and R. Juricevic
  Explicit upper bounds for \prod_{p\leq p_\omega(n)} \frac{p}{p-1}
  Contributions to Discrete Mathematics, 2(2):153-160, 2007.


• Z. Friggstad and S.L. Wismath
  Minimal Characteristic Algebras for k-Normality for Unary Types
  Journal of Applied Algebra and Discrete Structures, 3(2):65-89, 2005.

---

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):1-8, 2007


• H. Li and Z. Friggstad
  An Efficient Architecture for the AES Mix Columns Operation
  IEEE International Symposium on Circuits and Systems, 5:4637-4640, 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