Samir Khuller

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

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.

Publications

2011


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.
:71-82.

2010


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.
:1360-1372.

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.
:456-472.

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.

2009


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.
:69-77.

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.
:772-783.

2008


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.
:165-178.

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.

2007


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

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

2006


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.
:153-162.

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.
:811-828.

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

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

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.
:811-828.

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.
:1-12.

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.

2005


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

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.
:279-288.

2004


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

2003


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.

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.

2002


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.
:323-332.

2001


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.
:642-651.

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

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

2000


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.
:319-328.

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, Rosenfeld A, Wu A.  2000.  Centers of sets of pixels. Discrete Applied Mathematics. 103(1–3):297-306.

1999


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

1998


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

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

1997


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.

1996


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

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.

1995


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.
:593-604.

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

1994

1993


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.

1992

Pages