S. S. Ravi Ph.D., University of PittsburghDistinguished Teaching Professor
ravi@cs.albany.edu Computer Science Department, LI 67A University at Albany - State University of New York 1400 Washington Avenue Albany, NY 12222 (518) 442-4278 (518) 442-5638 (FAX) |

Personal Statement
of Research |

My main areas of interest are Design and Analysis of Algorithms, Data Mining, Wireless Networks, Operations Research, Discrete Dynamical Systems, Fault-Tolerant Computing and Very Large Scale Integration (VLSI). The main thrust of my research centers around the study of the algorithmic aspects of combinatorial optimization problems that arise in the above areas. For optimization problems that are computationally intractable, I also try to develop approximation algorithms with provable performance guarantees. |

Selected
Publications |

I. Davidson, M. Ester and S. S. Ravi,
,
Proc. ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining (KDD 2007), San Jose, CA, Aug. 2007.
Efficient Incremental Constrained Clustering |

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz, R. E. Stearns and M. Thakur,
,
Proc. International Joint Conference on Artificial
Intelligence (IJCAI 2007), Hyderabad, India, Jan. 2007, pp. 2268-2273.
Computational Aspects of Analyzing Social
Network Dynamics |

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Journal of Computer and System Sciences, Vol. 72, No. 8,
Dec. 2006, pp. 1317-1345.
Complexity of Reachability Problems for Finite Discrete
Dynamical Systems |

I. Davidson and S. S. Ravi,
,
Proceedings of the Twenty-First National Conference on Artificial
Intelligence (AAAI 2006), Boston, MA, July 2006.
Identifying and Generating Easy Sets of Constraints
for Clustering |

I. Davidson and S. S. Ravi,
,
Proc. 2005 SIAM International Conference on Data Mining (SDM 2005),
Newport Beach, CA, Apr. 2005, pp. 138-149.
(Winner of the best paper award.)
Clustering with Constraints: Feasibility Issues and the k-Means
Algorithm |

D. J. Rosenkrantz, S. Goel, S. S. Ravi and J. Gangolly,
,
Proc. Fifth European Dependable Computing Conference
(EDCC 2005), Budapest, Hungary, Apr. 2005,
Lecture Notes in Computer Science, Vol. 3463, pp. 345-362.
Structure-Based Resilience Metrics for Service-Oriented
Networks |

E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan and S. S. Ravi,
,
Mobile Networks and Applications (MONET),
Vol. 10, Issue 1-2, Feb.-Apr. 2005, pp. 19-34.
Algorithmic Aspects of Topology Control Problems for Ad Hoc
Networks |

C. L. Barrett, M. Drozda, M. V. Marathe, S. S. Ravi and J. P. Smith,
,
Scientific Programming, Vol. 12, No. 1, 2004, pp. 1-23.
A Mobility and Traffic Generation Framework for Modeling and
Simulating Ad hoc Communication Networks |

C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Annals of Combinatorics, Vol. 7, No. 4, 2003, pp. 381-408.
On Some Special Classes of Sequential Dynamical Systems |

H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi,
D. J. Rosenkrantz and R. E. Stearns,
,
Information and Computation, Vol. 173, No. 1, Feb. 2002,
pp. 40-63.
Parallel Approximation Schemes for a Class of Planar
and Near Planar Combinatorial Problems |

R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and
H. B. Hunt III,
,
Algorithmica, Vol. 31, No. 1, May 2001, pp. 58-78.
Approximation Algorithms for Degree-Constrained
Minimum-Cost Network-Design Problems |

K. B. Lakshmanan, D. J. Rosenkrantz and S. S. Ravi,
,
Theoretical Computer Science, Vol. 243, Issue 1-2, Jul. 2000,
pp. 269-288.
Alarm Placement in Systems with Fault Propagation |

M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz and
H. B. Hunt III,
,
Journal of Algorithms, Vol. 28, No. 1, July 1998, pp. 142-171.
Bicriteria Network Design Problems |

R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz and S. S. Ravi,
,
SIAM Journal on Discrete Mathematics, Vol. 9, No. 2,
May 1996, pp. 178-200.
Spanning Trees Short or Small |

D. C. Gu, D. J. Rosenkrantz and S. S. Ravi,
,
IEEE Transactions on Computers, Vol. 43, No. 6,
June 1994, pp. 641-650.
Construction of Check Sets for Algorithm-Based
Fault Tolerance |

S. S. Ravi, D. J. Rosenkrantz and G. K. Tayi,
,
Operations Research, Vol. 42, No. 2,
March-April 1994, pp. 299-310.
Heuristic and Special Case Algorithms for Dispersion
Problems |

S. Chakravarty, H. B. Hunt III, S. S. Ravi and D. J. Rosenkrantz,
,
IEEE Transactions on Computers,
Vol. 38, No. 6, June 1989, pp. 865-869.
The Complexity of Test Generation for PLAs and Monotone Combinationali
Circuits |

S. S. Ravi and E. L. Lloyd,
,
SIAM J. Computing, Vol. 17, No. 4,
Aug. 1988, pp. 696-710.
The Complexity of Near-Optimal PLA folding |