My recent research has been supported by NSF grants CCF 0430650, CCF 0728839 and a Google Research Award. I gratefully acknowledge their support.

My main interests are in designing efficient algorithms that can be used to solve optimization problems from different areas. Many problems in discrete optimization are NP-hard, and thus it is of interest to design effective heuristics to find sub-optimal solutions. One way of comparing heuristics is to compare the quality of the solutions they produce. Trying to design algorithms that produce solutions that are closer to optimal often leads to the design of better heuristics, as well as a much better understanding of the problem itself.

Data Migration: I have been working with Leana Golubchik and several students on various problems related to load balancing and data movement between storage devices. See our project page.

Sensor Networks: I have been working with Amol Deshpande and several students on various problems arising in the context of sensor networks. Problems are related to data migration, energy minimization etc.

Broadcast Scheduling: I have been interested in Broadcast Scheduling for almost a decade and have worked on a variety of objective functions.

Graph Algorithms: I have been interested in problems related primarily to network design.

Recent Papers.

Current Vistors and Postdocs:

• Hedyeh Beyhaghi
• Sumedha Uniyal

Current Graduate Students:

• Saba Ahmadi
• Pattara Sukprasert
• Sheng Yang

Current Undergraduate Students:

• Alexander Zhang
• Xi Chen

Current High School Students:

• Grace Cai

Graduated Students (Ph.D):

• Randeep Bhatia (Thesis Title: Approximation Algorithms for Scheduling Problems), Ph.D (August 1998). Currently at Bell Labs, NJ.
• Yoram Sussmann (Thesis Title: Approximation Algorithms for Facility Location Problems), Ph.D (Feb 1999). Currently at Iona College (New York).
• Rajiv Gandhi (Thesis Title: Broadcast Scheduling), Ph.D (May 2003). Currently at Rutgers University (Camden). Winner of a Fulbright, and several teaching awards.
• Michael Roberts (Thesis Title: A preprocessor for shotgun assembly of large genomes), Ph.D (2003). Work done under Jim Yorke's supervision.
• Yoo Ah Kim (Thesis Title: Algorithms for Data Migration), Ph.D (June 2005). PODS 2003 Best Newcomer Award. Currently at NIH.
• Justin Wan (Thesis Title: Algorithms for Data Dissemination and Collection), Ph.D (May 2005). PODS 2003 Best Newcomer Award. Currently at Google.
• Julian Mestre (Thesis Title: Primal-Dual Algorithms for Combinatorial Optimization Problems), Ph.D (Aug 2007). Currently at U. Sydney. Best Student Paper Award (SODA 2008).
• Srinivas Kashyap (Thesis Title: Algorithms for data placement, reconfiguration and monitoring in storage networks), Ph.D (Aug 2007). First job: Postdoc at IBM. Currently at Google.
• Azarakhsh Malekian (Thesis Title: Combinatorial problems in online advertising), Ph.D. (Dec 2009). First job: Postdoc at Northwestern. Currently at U. Toronto.
• Jian Li (Thesis Title: Decision making under Uncertainty), Ph.D. (Aug 2011). Committee Chair - A.Deshpande. Best papers at ESA 2010/VLDB 2009. IIIS, Tsinghua University.
• Barna Saha (Thesis Title: Approximation Algorithms for Resource Allocation), Ph.D. (Aug 2011). Best Paper Award at VLDB 2009. First job AT&T Labs. Now at U. Massachussets (Amherst).
• Saeed Alaei (Thesis Title: Mechanism design with general utilities), Ph.D (Aug 2012). First position: Postdoc at Cornell University. Now at Google Research (Mountain View).
• Jessica Chang (Thesis Title: Energy-Aware Batch Scheduling), Ph.D (U. Washington) (Aug 2013). Dept. of Defense.
• Koyel Mukherjee (Thesis Title: Algorithmic Approaches to Reducing Resource Costs in Data Centers), Ph.D (Dec 2013). Xerox Research Center India (Bangalore).
• Kanthi Sarpatwar (Thesis Title: Allocation Algorithms for Networks with Scarce Resouces), Ph.D (May 2015). IBM T. J. Watson Research Center.
• Manish Purohit (Thesis Title: Data-Aware Scheduling in Data Centers), Ph.D (May 2016). Google Research (Mountain View).
• Ioana Bercea (Thesis Title: Approximation Algorithms for Touring and Clustering Problems), Ph.D (July 2018). Postdoc at Tel-Aviv University (Israel).

• An Zhu Ph.D (Stanford) (Honors Thesis Title: A Uniform Framework for Weighted Connectivity Problems (Dorfman Award)). Winner of a Bell Labs fellowship,NSF fellowship. Currently at Google.
• Srinivas Kashyap Ph.D (Maryland) (Honors Thesis Title: Algorithms for Non-Uniform Size Data Placement for Parallel Disks.) Currently at Google.
• Svetlana Shargorodskaya (Honors Thesis Title: Implementation of Data Migration Algorithms)
• Colin Dixon Ph.D. (Washington) (Honors Thesis Title: Vertex Cover Problem with Hard Capacities) Currently at IBM.
• Jessica Chang Ph.D. (Washington) (Honors Thesis Title: Online Broadcast Scheduling: minimizing the maximum response time . NSF Graduate Fellowship. Phillip Merrill Scholarship and Honorable mention for the CRA Outstanding Undergraduate Award. Currently at University of Washington.
• Allie Hoch (undergrad) (Honors Thesis Title: On finding densest subgraphs and their applications). CRA Award (Honorable Mention). Winner of NSF Graduate fellowship. Joining UC Berekeley.
• Mitchell Katz (Google)
• Matt McCutchen (undergrad) (Honors Thesis Title: Streaming algorithms for k-center clusterings with outliers and anonymity). CRA Award for top undergraduate in 2010. Winner of Dorfman prize for undergraduate research and Stewart Research Award from the CS Dept. Currently doing his Ph.D. at MIT.
• Philip Anderson (undergrad) Joint with Louiqa Raschid.
• Elissa Redmiles (undergrad). CRA Award (Honorable Mention). Currently doing her Ph.D. at UMD.
• Deonna Hodges (FactSet)
• Naomi Wilcox (AOL)
• Alexa Greenberg (Google)
• Aboli Kumthekar (Appian)
• Chunxing Yin. Currently a graduate student at Georgia Tech.
• Megan Chao (MIT)
• Riley Murray (UC Berkeley). Currently a Ph.D. student at CalTech.
• Katherine Scola (Rutgers (Camden)). Currently a Ph.D. student at UMD.
• Ben Eggers (U. Washington). Applying to graduate school.
• Prayaag Venkat (UMD). Ph.D student at Harvard University.
• Kevin Sun (Rutgers). Ph.D. student at Duke.
• Pascal Sturmfels (U. Michigan). Ph.D. student at U. Washington.
• Jingling Li (Bryn Mawr College). Ph.D. student at UMD.
• Tu Luan (Bryn Mawr). Ph.D. student at UMD.
• Xi Chen (UMD). Currently a graduate student at Georgia Tech.
• Frederic Koehler (Princeton). Now a graduate student at MIT.
• Sam Estep
• Laurel Newman
• Ariel Fromm
• Galen Stetsyuk
• Mikhail Sorokin
• Raghav Gupta

Other (Ex-)Students I collaborate(d) with:

• Saurabh Kumar M.S, University of Maryland (2016). At Google.
• Tom Chan , M.S, University of Maryland (2013). At Palantir.
• Renars Gailis, M.S, University of Maryland (July 2003). Currently in Industry.
• Sudipto Guha Ph.D Stanford University, (August 2000). Currently Assoc. Professor at University of Pennsylvania.
• Abhishek Kashyap Ph.D, University of Maryland (Dec 2006). Currently in Industry.
• Martin Paraskevov M.S., University of Maryland (Aug 2008). Currently at Google.
• Robert Pless (Thesis Title: Video Linking), Ph.D (August 2000). Currently Assoc. Professor at Washington University at St. Louis.
• Suman Banerjee (Thesis Title: TBA), Ph.D (August 2003). Currently Asst. Professor at Univ of Wisconsin (Madison).
• Yuan Yao Ph.D (USC)
• Anju Rawat Ph.D (ECE UMD). Now at Intel.
• Michael Forbes Now an undergrad at MIT. Finalist at the Intel Science Talent Search!
• Frederic Koehler. Now an undergrad at Princeton. Finalist at the Intel Science Talent Search!
• Sharon Chen (Blair HS) Semi-Finalist at the Intel Science Talent Search!
• Samuel Zbarsky (Blair HS) Finalist at the Intel Science Talent Search!
• Matthew Das Sarma (Blair HS). Semi-finalist at Intel Science Talent Search. Now an undergrad at Stanford.
• Victor Xu. Undergrad at MIT.
• Eric Lu. Undergrad at CMU.
• Arman Siddique. Semi-finalist at Intel Science Talent Search. Undergrad at UMD.
• Grace Cai. Undergrad at MIT.

Projects done by other students:

• Tariq Magdon-Ismail Capacitated Vehicle Routing
• Jane Wang Node Weighted Steiner Trees