Sanjeev Khanna
Rosenbluth Faculty Fellow and Henry Salvatori Professor
Computer and Information Science (CIS)
Honors and Awards: S. Reid Warren Jr. Award - 2010
Research Expertise: Algorithms and Complexity
Sanjeev works in theoretical computer science, studying the amount of resources that are necessary and sufficient to perform a computational task. His specific interests are in fast computation of near-optimal solutions for NP-hard problems, a class which has eluded efficient exact algorithms. Ubiquitous in computer science and related disciplines, some representative examples of this class include multiprocessor scheduling, network design and routing, and the celebrated traveling salesman problem. Sanjeev's recent work has led to efficient algorithms for finding near-optimal solutions to several fundamental network design and routing problems.
Recent Publications 
- Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: Preface, Khanna, S., Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2013
- Using the crowd for top-k and group-by queries, Davidson, S.B. | Khanna, S. | Milo, T. | Roy, S., ACM International Conference Proceeding Series, 2013
- Mechanism design for a risk averse seller, Bhalgat, A. | Chakraborty, T. | Khanna, S., Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012
- The power of local information in social networks, Borgs, C. | Brautbar, M. | Chayes, J. | Khanna, S. | Lucier, B., Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012
- Improved hardness results for profit maximization pricing problems with unlimited supply, Chalermsook, P. | Chuzhoy, J. | Kannan, S. | Khanna, S., Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012