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 April, 2009).
- Z. Friggstad, M.R. Salavatipour, and Z.
Svitkina,
Asymmetric
Traveling Salesman Path and Directed Latency Problems,
To appear in SODA 2010. Manuscript 0907.0726v1 on
arxiv,
- I. Pirwani and M.R. Salavatipour,
A PTAS for
Minimum Clique Partition in Unit Disk Graphs,
Manuscript (Sept 2009). Earlier version 0904.2203 on
arxiv.
- N. Bansal, Z. Friggstad, R. Khandekar, and
M.R. Salavatipour,
A
Logarithmic Approximation for Unsplittable Flow on Line Graphs,
In Proceedings of SODA 2009.
- Z. Friggstad and M.R. Salavatipour,
Minimizing Movement in Mobile Facility
Location Problems
In Proceedings of FOCS 2008. Here
is the long version containing all the proofs.
- R. Khandekar, G. Kortsarz, V. Mirrokni, and
M.R. Salavatipour,
Two Stage
Robust Network Design
with Exponential Scenarios,
In Proceedings of ESA 2008.
- M.A. Safari and M.R. Salavatipour,
A
constant factor approximation for
minimum λ-edge-connected κ-subgraph with metric costs,
In Proceedings of APPROX 2008.
- Z. Friggstad and M.R. Salavatipour,
Approximability
of Packing Disjoint Cycles,
To appear in Algorithmica. 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.
Earlier version appeared in
Proceedings of ACM STOC 2007.
NOTE: The journal version
improves the ratio and corrects the proof of Theorem 3.1 of the
conference version.
- 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.
The Journal version which combines the results of this paper with our
FOCS 2006 paper titled
Approximation Algorithms for Non-Uniform
Buy-at-Bulk Network Design
To appear in SIAM J. on Computing.
- 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).
- C. Chekuri, M. Hajiaghayi, G. Kortsarz,
M.R.
Salavatipour,
Approximation
Algorithms for Non-Uniform Buy-at-Bulk Network Design problems,
In Proceedings of FOCS 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.
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,
Aug 2003.
- M.R. Salavatipour, On Sum Coloring
of Graphs ,
M.Sc thesis, Department of Computer Science, University of Toronto, Jan
2000.
- M.R. Salavatipour, Parallel Delauney
Triangulation ,
B.Sc thesis, Department of Computer Eng. , Sharif University of Tech.
(in persian).