Publications and Manuscripts

    Copyright note: For the papers that have been published, the copyright has been transferred to the respective publisher. Therefore, the paper cannot be copied or used for commercial purposes (updated Nov 2021).


    • Z. Friggstad, R. Mousavi, M. Rahgoshay, and M.R. Salavatipour,
      Improved Approximations for CVRP with Unsplittable Demands
      To appear in Proc. of IPCO 2022.

    • M. Rahgoshay and M.R. Salavatipour,
      Hierarchical Clustering: New Bounds and Objective

    • A. Jayaprakash and M.R. Salavatipour,
      Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
      To appear in TALG. Preliminary version in Proc. of SODA 2022.

    • H. Pang and M.R. Salavatipour,
      Approximation Algorithms for Generalized Path Scheduling
      Short version to appear in proceedings of ISAAC 2020.

    • D. Hyatt-Deneski, M. Rahgoshay and M.R. Salavatipour,
      Approximations for Throughput Maximization
      Short version in proceedings of ISAAC 2020.

    • M. Rahgoshay and M.R. Salavatipour,
      Asymptotic Quasi-polynomial Time Approximation Scheme for Resource Minimization for Fire Containment
      In Algorithmica (earlier version in Proc. of STACS 2020).

    • Z. Friggstad, K. Khodamoradi, and M.R. Salavatipour,
      Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means,
      In Proc. of SODA 2019.

    • Z. Friggstad, K. Khodamoradi, M. Rezapour, and M.R. Salavatipour,
      Approximation Schemes for Clustering with Outliers,
      ACM Transactions on Algorithms. Earlier version in Proceedings of SODA 2018. Complete version.

    • Z. Friggstad, A. Golestanian, K. Khodamoradi, C. Martin, M. Rahgoshay, M. Rezapour, and M.R. Salavatipour,
      Scheduling Problems over Network of Machines
      J. of Scheduling. earlier version in Proceedings of APPROX 2017.

    • C. Martin and M.R. Salavatipour,
      Approximation Algorithms for Capacitated k-tours
      In Algorithmica. Earlier version in Proceedings of ISAAC 2016.

    • Z. Friggstad, M. Rezapour, and M.R. Salavatipour,
      Local Search Yields a PTAS for k-Means in Doubling Metrics,
      To appear in special issue of SIAM J. on Computing (selected papers of FOCS'16). Earlier version in FOCS'16.

    • 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.

    • B. Behsaz, Z. Friggstad, M.R. Salavatipour, and R. Sivakumar
      Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median
      To appear in Algorithmica. Earlier version in Proceedings of ICALP 2015.

    • J. A. Soto, M. Rezapour, Z. Friggstad, and M. R. Salavatipour
      LP-based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
      To appear in Algorithmica. In Proceedings of WADS 2015.

    • S. Ahmadian, B. Behsaz, Z. Friggstad, A. Jorati, M.R. Salavatipour, and C. Swamy
      Approximation Algorithms for Minimum-Load k-Facility Location

      TALG 14(2), Article 16, 2018. Earlier version in Proceedings of APPROX 2014.

    • B. Behsaz, Z. Svitkina, and M.R. Salavatipour
      New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem
      Algorithmica 75(1): 53-83 (2016). Earlier version in Proceedings of SWAT 2012.

    • B. Behsaz and M.R. Salavatipour
      On Minimum Sum of Radii and Diameters Clustering
      Algorithmica 73(1): 143-165 (2015). Earlier version in Proceedings of SWAT 2012.

    • S. Har-Peled, A. Nayyeri, M.R. Salavatipour, and A. Sidiropoulos
      How to Walk Your Dog in the Mountains with No Magic Leash
      Discrete and Computational Geometry 55(1): 39-73 (2016). Earlier version in Proceedings of SoCG 2012.

    • M.R. Khani and M.R. Salavatipour,
      Improved Approximations for Buy-at-Bulk and Shallow-light k-Steiner trees and (k,2)-subgraph
      J. Comb. Optim. 31(2): 669-685 (2016). Earlier version in Proc. Of ISAAC 2011.
    • M.R. Khani and M.R. Salavatipour,
      Improved Approximation algorithms for Min-max Tree Cover and Bounded Tree Cover Problems
      Algorithmica 69(2): 443-460 (2014). Earlier version in Proc. Of APPROX 2011, LNCS 6845 pp 302-314.

    • I. Pirwani and M.R. Salavatipour,
      A PTAS for Minimum Clique Partition in Unit Disk Graphs,
      Algorithmica 62(3-4): 1050-1072 (2012). Earlier version in proceedings of SWAT 2010.

    • Z. Friggstad, M.R. Salavatipour, and Z. Svitkina,
      Asymmetric Traveling Salesman Path and Directed Latency Problems,
      SIAM J. Comput. 42(4): 1596-1619 (2013). Earlier version in Proc. of SODA 2010.

    • N. Bansal, Z. Friggstad, R. Khandekar, and M.R. Salavatipour,
      A Logarithmic Approximation for Unsplittable Flow on Line Graphs,
      ACM Trans. Algorithms 10(1): 1:1-1:15 (2014) Earlier version in Proc. of SODA 2009.

    • Z. Friggstad and M.R. Salavatipour,
      Minimizing movement in mobile facility location problems.

      ACM Transactions on Algorithms 7(3): 28 (2011). Earlier version in Proceedings of FOCS 2008.

    • R. Khandekar, G. Kortsarz, V. Mirrokni, and M.R. Salavatipour,
      Two Stage Robust Network Design with Exponential Scenarios,
      Algorithmica 65(2): 391-408 (2013). Earlier version in Proc. of ESA 2008.

    • M.A. Safari and M.R. Salavatipour,
      A constant factor approximation for minimum λ-edge-connected κ-subgraph with metric costs,
      SIAM J. Discrete Math. 25 (3): 1089-1102 (2011). Earlier version in Proceedings of APPROX 2008.

    • Z. Friggstad and M.R. Salavatipour,
      Approximability of Packing Disjoint Cycles,
      Algorithmica 60(2): 395-400 (2011). Earlier version appeared in Proceedings of ISAAC 2007.

    • L. Lau, S. Naor, M.R. Salavatipour, and M. Singh,
      Survivable Network Design with Degree or Order Constraints ,
      Invited to SIAM J. on Computing (special issue for selected papers of STOC'07) Vol.39, No.3 pp 1062-1087, 2009.
      Earlier version appeared in Proceedings of ACM STOC 2007.

    • O. Madani, W. Greiner, D. Kempe, and M.R. Salavatipour,
      Recall Systems: Efficient Learning and Use of Category Indices,
      In Proceedings of AISTATS 2007.

    • C. Chekuri, M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour,
      Approximation Algorithms for Node-Weighted Buy-at-Bulk Network Design Problems,
      In Proceedings of SODA 2007.

    • C. Chekuri, M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour,
      Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design
      In Proceedings of FOCS 2006.
      The Journal version which combines the results of SODA2007 and FOCS2006 papers In SIAM J. on Computing (5): 1772-1798 (2010)

    • Z. Cai, R. Goebel, M.R. Salavatipour, and G. Lin,
      Selecting dissimilar genes for multi-class classification, an application in cancer subtyping,
      BMC Bioinformatics 2007, 8:206.

    • Z. Cai, R. Goebel, M.R. Salavatipour, Y. Shi, L. Xu, and G. Lin,
      Selecting Genes with Dissimilar Discrimination Strength for Sample Class Prediction,
      In Proceedings of the Fifth Asia-Pacific Bioinformatics Conference (APBC 2007).

    • Z. Cai, L. Xu, Y. Shi, M. Salavatipour, R. Goebel, and G. Lin,
      Using Gene Clustering to Identify Discriminatory Genes with Higher Classification Accuracy.
      In Proceedings of IEEE 6th Symposium on Bioinformatics and Bioengineering (BIBE 2006).

    • M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour,
      Approximating Buy-at-Bulk and Shallow-light k-Steiner trees,
      Algorithmica 53(1): 89-103 (2009). Earlier version in Proceedings of APPROX 2006.

    • E. Demaine, U. Feige, M.T. Hajiaghayi, and M. R. Salavatipour,
      Combination Can Be Hard: Approximability of the Unique Coverage Problem,
      SIAM J. on Computing,  Volume 38, Issue 4, pp. 1464-1483. Prelimnary version in Proceedings of SODA 2006.

    • J. Cheriyan and M.R. Salavatipour,
      Packing Element-Disjoint Steiner Trees
      ACM Trans. on Algorithms. Volume 3,  Issue 4, Article No. 47. Preliminary version in proceedings of APPROX 2005.

    • M. Krivelevich, Z. Nutov, M.R. Salavatipour, J. Verstraete, and R. Yuster
      Approximation Algorithms and Hardness Results for Cycle Packing Problems ,
      ACM Transactions on Algorithms, Volume 3 , Issue 4,Article No. 48.
      Part of these results appeared in the following conference paper:

      M.R. Salavatipour and J. Verstraete,
      Disjoint Cycles: Integrality Gap, Hardness, and Approximation ,
      In Proceedings of IPCO 2005, LNCS volume 3509, pp 51-65.

    • J. Cheriyan and M.R. Salavatipour,
      Hardness and Approximation Results for Packing Steiner Trees,
      Algorithmica 45(1):21-43, 2006. The special issue for selected papers of ESA 2004.

    • M.R. Salavatipour
      Large Induced Forests in Triangle-free Planar Graphs ,
      Graphs and Combinatorics 22(1):113-126, 2006.

    • M. Molloy and M.R. Salavatipour,
      The Resolution Complexity of Random Constraint Satisfaction Problems ,
      SIAM J. on Computing 37(3): 895-922, 2007.
      A preliminary version appeared in Proceedings of FOCS 2003.

    • O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour.
      Planar Graphs without Cycles of Length from 4 to 7 are 3-colorable ,
      J. of Combinatorial Theory (Series B), 93:303-311, 2005.

    • K. Jain, M. Mahdian, and M.R. Salavatipour,
      Packing Steiner Trees ,
      In Proceedings of SODA 2003.

    • M.R. Salavatipour,
      A Polynomial Time Algorithm for Strong Edge Coloring of Partial k-Trees ,
      Discrete Applied Mathematics 143:(1-3) 2004, pp 285-291.

    • M.R. Salavatipour,
      A (1+ε)-Approximation Algorithm for Partitioning Hypergraphs Using A New Algorithmic Version of the Lovasz Local Lemma ,
      Random Structures and Algorithms 25(1) 2004, pp 68-90.
      Earlier version appeared in Proceedings of SODA 2003.

    • M. Molloy and M.R. Salavatipour,
      A Bound on the Chromatic Number of the Square of a Planar Graph,
      J. of Combinatorial Theory (Series B), Volume 94(2), pp 189-213, 2005.
      Conference version was:
      Frequency Channel Assignment on Planar Networks , In Proceedings of ESA 2002, LNCS 2461, pp. 736-747.

    • M.R. Salavatipour,
      The Three Color Problem For Planar Graphs ,
      Technical Report CSRG-458, Department of Computer Science, University of Toronto, July 2002. Also available here .
      Here are the supplementary material for this paper.

    • M.R. Salavatipour,
      On Sum Coloring of Graphs ,
      Discrete Applied Math. 127(3), 477-488, 2003.

    • M. Mahdian, E.S. Mahmoodian, A. Saberi, M.R. Salavatipour, and R. Touserkani,
      On a Conjecture of Keedwell and the Cycle Double Cover Conjecture,
      Disc. Math. 216: (1-3), pp 287-292, 2000.


    Theses

    • M.R. Salavatipour,
      Graph Colouring via the Discharging Method
      Ph.D. thesis, Department of Computer Science, University of Toronto, 2003.

    • M.R. Salavatipour,
      On sum coloring of graphs
      M.Sc. thesis, Department of Computer Science, University of Toronto, 2000.

    • M.R. Salavatipour,
      Parallel Delauney Triangulation ,
      B.Sc thesis, Department of Computer Eng. , Sharif University of Tech. (in persian).