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