Sartaj K. Sahni

Sartaj K. Sahni is a Distinguished Professor and Chair of Computer and Information Sciences and Engineering at the University of Florida. He is also a member of the European Academy of Sciences, a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute, and a Distinguished Alumnus of the Indian Institute of Technology, Kanpur. Dr. Sahni received his B.Tech. (Electrical Engineering) degree from the Indian Institute of Technology, Kanpur, and the M.S. and Ph.D. degrees in Computer Science from Cornell University. Dr. Sahni has published over two hundred and fifty research papers and written 15 texts.

His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, scheduling, computational geometry, image processing, matrix algebra, design automation, and medical algorithms. His texts on data structures and algorithms have been very popular worldwide for the past 25 years.

Dr. Sahni is a co-editor-in-chief of the Journal of Parallel and Distributed Computing, a managing editor of the International Journal of Foundations of Computer Science, and a member of the editorial boards of Computer Systems: Science and Engineering and Parallel Processing Letters. He has served as program committee chair, general chair, and been a keynote speaker at many conferences.

Dr. Sahni has supervised more than thirty Ph.D. dissertations. Many of the accomplishments described below resulted from collaborations with these Ph.D. students.

Dr. Sahni was a pioneer in the area of NP-hard/NP-complete problems. He initiated the study of NP-hard problems (as opposed to NP-complete ones) and expanded the realm of these computationally difficult problems to include optimization problems from network flows, game theory, and electronic computer-aided design (ECAD). The introduction of NP-hard problems permitted one to talk about the complexity of naturally occurring optimization problems without having to go through the artifact of a corresponding unnatural decision problem. This, in turn, enhanced the accessibility of the research in the area to those interested in optimization.

Dr. Sahni was amongst the first to show that certain NP-hard problems could be solved approximately by fast algorithms. He was the first to show that some approximation problems are also NP-hard. Another important development in this area that is due to Dr. Sahni is the discovery of general techniques to obtain fully polynomial time approximation schemes for a wide class of NP-hard problems. This made it possible to solve a large class of NP-hard problems by mechanically generated approximation algorithms. Furthermore, these mechanically generated approximation algorithms could generate solutions whose value is as close to optimal as is desired. The complexity of these approximation algorithms is polynomial in the problem size and the reciprocal of the desired proximity to optimal. Dr. Sahni also proposed the first sub-exponential algorithm for an NP-hard problem. Since virtually all disciplines of engineering, science, and the social sciences are now known to have NP-hard problems, Dr. Sahni's pioneering work in the area has directly or indirectly impacted a very broad spectrum of research and practice.

In the area of multiprocessor scheduling, Dr. Sahni has introduced and studied several models (open shop; independent uniform machines; independent unrelated machines; and master-slave processors) that have found significant application in the scheduling of parallel computers and a network of heterogeneous computers as well as in many industrial manufacturing settings. These models have subsequently been studied by many other researchers and are now included in virtually all scheduling texts.

In the ECAD area, Dr. Sahni was the first to investigate the study of complexity issues and he popularized the concepts of NP-hardness and asymptotic complexity analysis in this field. He demonstrated the merits of showing a problem NP-hard before developing heuristics and of performing an asymptotic analysis of the proposed algorithm/heuristic. In parallel computing, Dr. Sahni has developed most of the fundamental data routing algorithms for mesh and hypercube computers. He formulated and studied the Random Access Read (RAR) and Write (RAW) operations, which are the fundamental building blocks for many of today's parallel algorithms. He formulated the class of bit-permute-complement permutations and showed how these can be done optimally on a mesh computer. This class includes almost all of the commonly performed permutations such as transpose, reverse, and shuffle. Besides opening new research directions, Dr. Sahni's research in the areas of NP-hard problems, multiprocessor scheduling, complexity of ECAD problems, and parallel computing has become common classroom material and can be found in most popular texts on these subjects.