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