Samir Khuller

3369 A.V. Williams Building
(301) 405-6765
Ph.D., Cornell University
Special Awards/Honors: 
NSF Career Award, University Maryland Distinguished Scholar-Teacher

Samir Khuller is a professor in the Department of Computer Science.

His research interests are broadly in combinatorial optimization with a focus on graph algorithms, discrete optimization, and data storage management. Khuller has published many journal and conference papers, and several book chapters on these topics. He was the PC Chair for the 2000 Approximation Algorithms for Combinatorial Optimization Problems (APPROX) Conference and served on the ACM Symposium on Theory of Computing (STOC) 2003 committee, as well as the committees for the 1997 and 2007 ACM-SIAM Symposium on Discrete Algorithms (SODA) Conference.

Khuller received the National Science Foundation (NSF) CAREER Award, the Dean's Teaching Excellence Award, and also a CTE-Lilly Teaching Fellowship. In 2003, he and his students were awarded the "Best newcomer paper" award for the ACM Principles of Database Systems (PODS) Conference. He received the University of Maryland's Distinguished Scholar Teacher Award in 2007 and a Google Research Award. He is an editor for the journals, Networks and Algorithmica.

Khuller received his undergraduate degree from IIT Kanpur, and his doctorate from Cornell University in 1990. He spent two years as a research associate at UMIACS, before joining the Department of Computer Science. He was the associate chair for graduate studies from 2004 to 2008.

Go here to view Khuller's academic publications on Google Scholar.



Deshpande A, Khuller S, Malekian A, Toossi M.  2011.  Energy efficient monitoring in sensor networks. Algorithmica. 59(1):94-114.

Chekuri C, Gal A, Im S, Khuller S, Li J, McCutchen R, Moseley B, Raschid L.  2011.  New models and algorithms for throughput maximization in broadcast scheduling. Approximation and Online Algorithms.


Khuller S, Kim YA, Wan YCJ.  2010.  Broadcasting on networks of workstations. Algorithmica. 57(4):848-868.

Khuller S, Li J, Saha B.  2010.  Energy efficient scheduling via partial shutdown. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms.

Saha B, Hoch A, Khuller S, Raschid L, Zhang XN.  2010.  Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. Research in Computational Molecular Biology.

Aggarwal G, Panigrahy R, Feder T, Thomas D, Kenthapadi K, Khuller S, Zhu A.  2010.  Achieving anonymity via clustering. ACM Trans. Algorithms. 6(3):49:1–49:19-49:1–49:19.


Alaei S, Arcaute E, Khuller S, Ma W, Malekian A, Tomlin J.  2009.  Online allocation of display advertisements subject to advanced sales contracts. Proceedings of the Third International Workshop on Data Mining and Audience Intelligence for Advertising.

Li J, Deshpande A, Khuller S.  2009.  Minimizing Communication Cost in Distributed Multi-query Processing. IEEE 25th International Conference on Data Engineering, 2009. ICDE '09.


Matthew McCutchen R, Khuller S.  2008.  Streaming algorithms for k-center clustering with outliers and with anonymity. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques.

Deshpande A, Khuller S, Malekian A, Toossi M.  2008.  Energy Efficient Monitoring in Sensor Networks. LATIN 2008: Theoretical InformaticsLATIN 2008: Theoretical Informatics. 4957:436-448.


Khuller S, Malekian A, Mestre J.  2007.  To fill or not to fill: the gas station problem. Algorithms–ESA 2007.

Khuller S, Martinez V, Nau DS, Simari G, Sliva A, Subrahmanian V.  2007.  Finding most probable worlds of probabilistic logic programs. Scalable Uncertainty Management.


Kashyap A, Khuller S, Shayman M.  2006.  Relay Placement for Higher Order Connectivity in Wireless Sensor Networks. INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings.

Gandhi R, Khuller S, Parthasarathy S, Srinivasan A.  2006.  Dependent rounding and its applications to approximation algorithms. Journal of the ACM. 53(3):324-360.

Aggarwal G, Feder T, Kenthapadi K, Khuller S, Panigrahy R, Thomas D, Zhu A.  2006.  Achieving anonymity via clustering. Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.

Bleiholder J, Khuller S, Naumann F, Raschid L, Wu Y.  2006.  Query planning in the presence of overlapping sources. Advances in Database Technology-EDBT 2006.

Charikar M, Khuller S.  2006.  A robust maximum completion time measure for scheduling. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm.

Khuller S, Kim YA, Malekian A.  2006.  Improved algorithms for data migration. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques.

Rohloff KR, Khuller S, Kortsarz G.  2006.  Approximating the minimal sensor selection for supervisory control. Discrete Event Dynamic Systems. 16(1):143-170.

Gandhi R, Halperin E, Khuller S, Kortsarz G, Srinivasan A.  2006.  An improved approximation algorithm for vertex cover with hard capacities. Journal of Computer and System Sciences. 72(1):16-33.

Bleiholder J, Khuller S, Naumann F, Raschid L, Wu Y.  2006.  Query planning in the presence of overlapping sources. Advances in Database Technology-EDBT 2006.


Khuller S, Lee K, Shayman M.  2005.  On degree constrained shortest paths. Algorithms–ESA 2005.

Khuller S, Kim Y-A, Wan Y-C J.  2005.  Broadcasting on networks of workstations. Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures.


Golubchik L, Khuller S, Kim YA, Shargorodskaya S, Wan YC.  2004.  Data migration on parallel disks. Algorithms–ESA 2004.


Golubchik L, Cheng WC, Chou CF, Khuller S, Samet H, Wan YCJ.  2003.  Digital Government-Bistro: A Scalable and Secure Data Transfer Service for Digital Government Applications. Communications of the ACM-Association for Computing Machinery-CACM. 46(1):50-51.

Golubchik L, Cheng WC, Chou C-F, Khuller S, Samet H, Wan JC.  2003.  Bistro: a scalable and secure data transfer service for digital government applications. Communications of the ACM. 46(1):50-51.

Banerjee S, Kommareddy C, Kar K, Bhattacharjee B, Khuller S.  2003.  Construction of an efficient overlay multicast infrastructure for real-time applications. INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. 2:1521-1531vol.2-1521-1531vol.2.


Gandhi R, Khuller S, Parthasarathy S, Srinivasan A.  2002.  Dependent rounding in bipartite graphs. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.


Gandhi R, Khuller S, Srinivasan A.  2001.  Approximation algorithms for partial covering problems. Automata, Languages and Programming.

Ben-Yashar R, Khuller S, Kraus S.  2001.  Optimal collective dichotomous choice under partial order constraints. Mathematical Social Sciences. 41(3):349-364.

Hassin R, Khuller S.  2001.  z-Approximations. Journal of Algorithms. 41(2):429-442.

Charikar M, Khuller S, Mount D, Narasimhan G.  2001.  Algorithms for facility location problems with outliers. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms.


Khuller S, Rosenfeld A, Wu A.  2000.  Centers of sets of pixels. Discrete Applied Mathematics. 103(1–3):297-306.

Khuller S, Sussmann YJ.  2000.  The capacitated k-center problem. SIAM Journal on Discrete Mathematics. 13:403-403.

Khuller S, Bhatia R, Pless R.  2000.  On local search and placement of meters in networks. Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms.

Bhatia R, Khuller S, Naor J(S).  2000.  The Loading Time Scheduling Problem. Journal of Algorithms. 36(1):1-33.

Khuller S, Pless R, Sussmann YJ.  2000.  Fault tolerant K-center problems. Theoretical Computer Science. 242(1–2):237-245.


Khuller S, Moss A, Naor JS.  1999.  The budgeted maximum coverage problem. Information Processing Letters. 70(1):39-45.


Guha S, Khuller S.  1998.  Greedy strikes back: improved facility location algorithms. Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms.

Khuller S, Sussmann YJ, Bhatia R, Guha S.  1998.  Facility Location with Dynamic Distance Functions. Journal of Combinatorial Optimization. 2(3):199-217.

Khuller S, Raghavachari B, Young N.  1998.  Low Degree Spanning Trees of Small Weight. UMIACS-TR-94-1


Fekete SP, Khuller S, Klemmstein M, Raghavachari B, Young N.  1997.  A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. Journal of Algorithms. 24(2):310-324.


Khuller S, Raghavachari B.  1996.  Graph and network algorithms. ACM Computing Surveys. 28(1):43-45.

Khuller S, Raghavachari B, Young N.  1996.  On strongly connected digraphs with bounded cycle length. Discrete Applied Mathematics. 69(3):281-289.

Khuller S, Raghavachari B, Rosenfeld A.  1996.  Landmarks in graphs. Discrete Applied Mathematics. 70(3):217-229.


Khuller S, Raghavachari B.  1995.  Improved approximation algorithms for uniform connectivity problems. Proceedings of the twenty-seventh annual ACM symposium on Theory of computing.

Khuller S, Matias Y.  1995.  A simple randomized sieve algorithm for the closest-pair problem. Information and Computation. 118(1):34-37.

Khuller S, Raghavachari B, Young N.  1995.  Approximating the minimum equivalent digraph. SIAM Journal on Computing (SICOMP). 24(4):859-872.

Khuller S, Raghavachari B, Young N.  1995.  Balancing minimum spanning trees and shortest-path trees. Algorithmica. 14(4):305-321.

Khuller S, Rivlin E, Rosenfeld A.  1995.  Graphbots: Mobility in discrete spaces. Automata, Languages and Programming.



Arkin EM, Khuller S, Mitchell JSB.  1993.  Geometric knapsack problems. Algorithmica. 10(5):399-427.

Khuller S, Naor JS, Klein P.  1993.  The lattice structure of flow in planar graphs. SIAM Journal on Discrete Mathematics. 6:477-477.

Khuller S, Thurimella R.  1993.  Approximation Algorithms for Graph Augmentation. Journal of Algorithms. 14(2):214-225.