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.
Go here to view Khuller's academic publications on Google Scholar.
Publications
2011
2011. Energy efficient monitoring in sensor networks. Algorithmica. 59(1):94-114.
2011. New models and algorithms for throughput maximization in broadcast scheduling. Approximation and Online Algorithms. :71-82.
2010
2010. On Computing Compression Trees for Data Collection in Wireless Sensor Networks. 2010 Proceedings IEEE INFOCOM. :1-9.
2010. Achieving anonymity via clustering. ACM Trans. Algorithms. 6(3):49:1–49:19-49:1–49:19.
2010. Broadcasting on networks of workstations. Algorithmica. 57(4):848-868.
2010. Energy efficient scheduling via partial shutdown. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. :1360-1372.
2010. Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. Research in Computational Molecular Biology. :456-472.
2009
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.
2009. Minimizing Communication Cost in Distributed Multi-query Processing. IEEE 25th International Conference on Data Engineering, 2009. ICDE '09. :772-783.
2009. On Computing Compression Trees for Data Collection in Sensor Networks. arXiv:0907.5442.
2008
2008. Efficient and Resilient Backbones for Multihop Wireless Networks. Mobile Computing, IEEE Transactions on. 7(11):1349-1362.
2008. An Optimal Incremental Algorithm for Minimizing Lateness with Rejection. Algorithms-ESA 2008. :601-610.
2008. Streaming algorithms for k-center clustering with outliers and with anonymity. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. :165-178.
2008. Energy Efficient Monitoring in Sensor Networks. LATIN 2008: Theoretical InformaticsLATIN 2008: Theoretical Informatics. 4957:436-448.
2007
2007. To fill or not to fill: the gas station problem. Algorithms–ESA 2007. :534-545.
2007. Finding most probable worlds of probabilistic logic programs. Scalable Uncertainty Management. :45-59.
2006
2006. A robust maximum completion time measure for scheduling. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. :324-333.
2006. Improved algorithms for data migration. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. :164-175.
2006. Approximating the minimal sensor selection for supervisory control. Discrete Event Dynamic Systems. 16(1):143-170.
2006. An improved approximation algorithm for vertex cover with hard capacities. Journal of Computer and System Sciences. 72(1):16-33.
2006. Query planning in the presence of overlapping sources. Advances in Database Technology-EDBT 2006. :811-828.
2006. Approximation algorithms for channel allocation problems in broadcast networks. Networks. 47(4):225-236.
2006. Relay Placement for Higher Order Connectivity in Wireless Sensor Networks. INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings. :1-12.
2006. Dependent rounding and its applications to approximation algorithms. Journal of the ACM. 53(3):324-360.
2006. Algorithms for non-uniform size data placement on parallel disks. Journal of Algorithms. 60(2):144-167.
2006. OMNI: An efficient overlay multicast infrastructure for real-time applications. Computer Networks. 50(6):826-841.
2006. Achieving anonymity via clustering. Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. :153-162.
2006. Query planning in the presence of overlapping sources. Advances in Database Technology-EDBT 2006. :811-828.
2005
2005. On degree constrained shortest paths. Algorithms–ESA 2005. :259-270.
2005. Broadcasting on networks of workstations. Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures. :279-288.
2004
2004. Approximation algorithms for partial covering problems. Journal of Algorithms. 53(1):55-84.
2004. Data migration on parallel disks. Algorithms–ESA 2004. :689-701.
2004. Equivalence of two linear programming relaxations for broadcast scheduling. Operations Research Letters. 32(5):473-478.
2003
2003. Bistro: a scalable and secure data transfer service for digital government applications. Commun. ACM. 46(1):50-51.
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.
2003. Bistro: a scalable and secure data transfer service for digital government applications. Communications of the ACM. 46(1):50-51.
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.
2002
2002. Dependent rounding in bipartite graphs. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. :323-332.
2001
2001. Algorithms for facility location problems with outliers. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. :642-651.
2001. Approximation algorithms for partial covering problems. Automata, Languages and Programming. :225-236.
2001. Optimal collective dichotomous choice under partial order constraints. Mathematical Social Sciences. 41(3):349-364.
2001. z-Approximations. Journal of Algorithms. 41(2):429-442.
2000
2000. Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica. 28(4):422-437.
2000. The capacitated k-center problem. SIAM Journal on Discrete Mathematics. 13:403-403.
2000. On local search and placement of meters in networks. Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. :319-328.
2000. The Loading Time Scheduling Problem. Journal of Algorithms. 36(1):1-33.
2000. Fault tolerant K-center problems. Theoretical Computer Science. 242(1–2):237-245.
2000. Centers of sets of pixels. Discrete Applied Mathematics. 103(1–3):297-306.
1999
1999. The budgeted maximum coverage problem. Information Processing Letters. 70(1):39-45.
1999. Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. Information and Computation. 150(1):57-74.
1998
1998. Approximation algorithms for connected dominating sets. Algorithmica. 20(4):374-387.
1998. Greedy strikes back: improved facility location algorithms. Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms. :649-657.
1998. Facility Location with Dynamic Distance Functions. Journal of Combinatorial Optimization. 2(3):199-217.
1998. Low Degree Spanning Trees of Small Weight. UMIACS-TR-94-1
1997
1997. A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. Journal of Algorithms. 24(2):310-324.
1996
1996. Graph and network algorithms. ACM Computing Surveys. 28(1):43-45.
1996. On strongly connected digraphs with bounded cycle length. Discrete Applied Mathematics. 69(3):281-289.
1996. Landmarks in graphs. Discrete Applied Mathematics. 70(3):217-229.
1995
1995. A simple randomized sieve algorithm for the closest-pair problem. Information and Computation. 118(1):34-37.
1995. Approximating the minimum equivalent digraph. SIAM Journal on Computing (SICOMP). 24(4):859-872.
1995. Balancing minimum spanning trees and shortest-path trees. Algorithmica. 14(4):305-321.
1995. Graphbots: Mobility in discrete spaces. Automata, Languages and Programming. :593-604.
1995. Improved approximation algorithms for uniform connectivity problems. Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. :1-10.
1994
1994. Biconnectivity approximations and graph carvings. Journal of the ACM (JACM). 41(2):214-235.
1994. Flow in planar graphs with vertex capacities. Algorithmica. 11(3):200-225.
1994. A primal-dual parallel approximation technique applied to weighted set and vertex covers. Journal Algorithms. 17(2):280-289.
1993
1993. Geometric knapsack problems. Algorithmica. 10(5):399-427.
1993. The lattice structure of flow in planar graphs. SIAM Journal on Discrete Mathematics. 6:477-477.
1993. Approximation Algorithms for Graph Augmentation. Journal of Algorithms. 14(2):214-225.
1992
1992. Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. SIAM Journal on Computing. 21:486-486.