Approximation Schemes for Clustering with Outliers,

In Proceedings of SODA 2018. Complete version.

- Scheduling
Problems over Network of Machines

In Proceedings of APPROX 2017. Complete version.

Approximation Algorithms for Capacitated k-tours

In Algorithmica. Earlier version in Proceedings of ISAAC 2016.

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.

- Approximating
Connected Facility Location with Lower and Upper Bounds
via LP Rounding

In Proceedings of SWAT 2016.

- Approximation
Algorithms for Min-Sum k-Clustering and Balanced k-Median

To appear in Algorithmica. Earlier version in Proceedings of ICALP 2015.

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

Also,*Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design*

In Proceedings of FOCS 2006.

The Journal version which combines the results of these 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. -
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).

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 Sept 2017).

Theses