S. S. Ravi Ph.D., University of Pittsburgh
Distinguished 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, Efficient Incremental Constrained Clustering, Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2007), San Jose, CA, Aug. 2007.
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns and M. Thakur, Computational Aspects of Analyzing Social Network Dynamics, Proc. International Joint Conference on Artificial Intelligence (IJCAI 2007), Hyderabad, India, Jan. 2007, pp. 2268-2273.
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Complexity of Reachability Problems for Finite Discrete Dynamical Systems, Journal of Computer and System Sciences, Vol. 72, No. 8, Dec. 2006, pp. 1317-1345.
I. Davidson and S. S. Ravi, Identifying and Generating Easy Sets of Constraints for Clustering, Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI 2006), Boston, MA, July 2006.
I. Davidson and S. S. Ravi, Clustering with Constraints: Feasibility Issues and the k-Means Algorithm, Proc. 2005 SIAM International Conference on Data Mining (SDM 2005), Newport Beach, CA, Apr. 2005, pp. 138-149. (Winner of the best paper award.)
D. J. Rosenkrantz, S. Goel, S. S. Ravi and J. Gangolly, Structure-Based Resilience Metrics for Service-Oriented Networks, Proc. Fifth European Dependable Computing Conference (EDCC 2005), Budapest, Hungary, Apr. 2005, Lecture Notes in Computer Science, Vol. 3463, pp. 345-362.
E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan and S. S. Ravi, Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks, Mobile Networks and Applications (MONET), Vol. 10, Issue 1-2, Feb.-Apr. 2005, pp. 19-34.
C. L. Barrett, M. Drozda, M. V. Marathe, S. S. Ravi and J. P. Smith, A Mobility and Traffic Generation Framework for Modeling and Simulating Ad hoc Communication Networks, Scientific Programming, Vol. 12, No. 1, 2004, pp. 1-23.
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, On Some Special Classes of Sequential Dynamical Systems, Annals of Combinatorics, Vol. 7, No. 4, 2003, pp. 381-408.
H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Problems, Information and Computation, Vol. 173, No. 1, Feb. 2002, pp. 40-63.
R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and H. B. Hunt III, Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems, Algorithmica, Vol. 31, No. 1, May 2001, pp. 58-78.
K. B. Lakshmanan, D. J. Rosenkrantz and S. S. Ravi, Alarm Placement in Systems with Fault Propagation, Theoretical Computer Science, Vol. 243, Issue 1-2, Jul. 2000, pp. 269-288.
M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz and H. B. Hunt III, Bicriteria Network Design Problems, Journal of Algorithms, Vol. 28, No. 1, July 1998, pp. 142-171.
R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz and S. S. Ravi, Spanning Trees Short or Small, SIAM Journal on Discrete Mathematics, Vol. 9, No. 2, May 1996, pp. 178-200.
D. C. Gu, D. J. Rosenkrantz and S. S. Ravi, Construction of Check Sets for Algorithm-Based Fault Tolerance, IEEE Transactions on Computers, Vol. 43, No. 6, June 1994, pp. 641-650.
S. S. Ravi, D. J. Rosenkrantz and G. K. Tayi, Heuristic and Special Case Algorithms for Dispersion Problems, Operations Research, Vol. 42, No. 2, March-April 1994, pp. 299-310.
S. Chakravarty, H. B. Hunt III, S. S. Ravi and D. J. Rosenkrantz, The Complexity of Test Generation for PLAs and Monotone Combinationali Circuits, IEEE Transactions on Computers, Vol. 38, No. 6, June 1989, pp. 865-869.
S. S. Ravi and E. L. Lloyd, The Complexity of Near-Optimal PLA folding, SIAM J. Computing, Vol. 17, No. 4, Aug. 1988, pp. 696-710.