Sartaj Kumar Sahni (* 22. Juli 1949 in Poona^[1]) ist ein indisch-US-amerikanischer Informatiker, der sich mit Algorithmen und Datenstrukturen befasst.

Sahni studierte Elektrotechnik am Indian Institute of Technology Kanpur (Bachelor 1970) und an der Cornell University, wo er 1972 seinen Master-Abschluss in Informatik machte und 1973 bei Ellis Horowitz promoviert wurde (On the knapsack and other computational related problems)^[2]. 1973 wurde er Assistant Professor, 1977 Associate Professor und 1980 Professor an der University of Minnesota. Seit 1990 ist er Professor an der University of Florida, wo er 2001 bis 2011 der Informatik-Fakultät vorstand.

Sahni befasste sich unter anderem mit Parallelalgorithmen zum Beispiel zur Matrizenmultiplikation, Scheduling, Verbindungsnetzwerke von Rechnern und Netzwerkalgorithmen, Bildverarbeitung, automatisiertem Design elektronischer Schaltkreise, rechnergestützter Geometrie (Computational Geometry), medizinische Algorithmen speziell in der Strahlentherapie. Er war ein Pionier in der Untersuchung NP-schwerer (NP-hard) Probleme^[3] und untersuchte solche Probleme bei Optimierungsaufgaben zum Beispiel in Netzwerkflüssen, Spieltheorie und CAD und bestimmten Approximationsproblemen. Er fand allgemeine Methoden zum Finden polynomzeitlicher Näherungsalgorithmen für eine große Klasse NP-schwieriger Probleme^[4]. Er fand als erster einen subexponentiellen Algorithmus für ein NP-schwieriges Problem.

Er ist Mitherausgeber des Journal of Parallel and Distributed Computing und Herausgeber des International Journal of Foundations of Computer Science. Er ist mit seinem Lehrer Ellis Horowitz Autor zweier verbreiteter Lehrbücher über Algorithmen bzw. Datenstrukturen und erhielt für seine Lehre den IEEE Taylor L. Booth Education Award.

2003 erhielt er den W. Wallace McDowell Award für Beiträge zur Theorie NP-schwerer und NP-vollständiger Probleme. 1988 wurde er Fellow der IEEE, der Association for Computing Machinery und der American Association for the Advancement of Science. Er ist Mitglied der European Academy of Sciences. 2001 erhielt er den Distinguished Alumnus Award des Indian Institute of Technology.

• mit Ellis Horowitz Fundamentals of Computer Algorithms, Computer Science Press, Maryland 1978, Neuauflage mit Sanguthevar Rajasekaran, Freeman, 1998, 2. Auflage Silicon Press 2008 (es gibt auch eine C++ Ausgabe), Deutsche Ausgabe Algorithmen. Entwurf und Analyse, Springer 1981
• mit Horowitz Fundamentals of Data Structures, Computer Science Press 1976, Erweiterte Ausgabe mit Susan Anderson-Freed, Freeman 1983, 2. Auflage Silicon Press (es gibt auch Ausgaben für C++, Pascal und Turbo-Pascal)
  • Deutsche Ausgabe: Grundlagen von Datenstrukturen in C, Redline 1998
• mit Sanjay Ranka Hypercube algorithms with applications to image processing and pattern recognition, Springer Verlag, New York, 1990
• mit Robert Cmelik Software Development in C, Silicon Press, New Jersey, 1995
• mit Raj Kumar Software Development in Java, Silicon Press, New Jersey, 2003

• Homepage
• Biographie anlässlich des McDowell Award

1. ↑ Lebensdaten nach American Men and Women of Science, Thomson Gale 2005
2. ↑ Mathematics Genealogy Project
3. ↑ Eingeführt (als P-schwer) in Sahni Computationally related problems, SIAM J. Comput., Band 3, 1974, S. 262–279
4. ↑ Sahni General techniques for combinatorial approximation, Operations Research, Band 25, 1977, S. 920–936, Abstract