Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means,

To appear in Proc. of SODA 2019.

Approximation Schemes for Clustering with Outliers,

In Proceedings of SODA 2018. Complete version.

- Scheduling
Problems over Network of Machines

In Proceedings of APPROX 2017. Full version to appear in J. of Scheduling.

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 July 2018).

Theses