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