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