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.

I particularly enjoy working with students at all levels - Ph.D. students, M.S. students, Undergraduates, and High School students. I am currently actively advising four Ph.D. students, and three undergraduates.

Recent Papers.

Current (Grad and Undergrad) Students:

• Saeed Alaei
• Jian Li Co-advised with Amol Deshpande
• Barna Saha
• Matt McCutchen (undergrad)
• Allie Hoch (undergrad)
• Mitchell Katz (undergrad)

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).
• 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). Currently at U. Connecticut.
• Justin Wan (Thesis Title: Algorithms for Data Dissemination and Collection), Ph.D (May 2005). Currently at Google.
• Julian Mestre (Thesis Title: Primal-Dual Algorithms for Combinatorial Optimization Problems), Ph.D (Aug 2007). Currently at Max Planck Institute. Best Student Paper Award (SODA 2008).
• Srinivas Kashyap (Thesis Title: Algorithms for data placement, reconfiguration and monitoring in storage networks), Ph.D (Aug 2007). Currently at IBM T. J. Watson Research Center.
• Azarakhsh Malekian (Thesis Title: Combinatorial problems in online advertising), Ph.D. (Dec 2009). Postdoc at Northwestern University.

• 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 IBM T J Watson.
• Svetlana Shargorodskaya (Honors Thesis Title: Implementation of Data Migration Algorithms)
• Colin Dixon (Honors Thesis Title: Vertex Cover Problem with Hard Capacities) Currently at University of Washington.
• Jessica Chang (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.

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

• 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).
• Michael Forbes Now an undergrad at MIT. Finalist at the Intel Science Talent Search!

Projects done by other students:

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