My main interests are in designing efficient graph theoretic 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. Most of my recent work is in graph algorithms and discrete optimization. I have also been working with Leana Golubchik on various problems related to load balancing and data movement between storage devices. See our project page.

Recent Papers.

Grant Page (with papers)

Technical Reports .

Graduated Students (Ph.D):

• Randeep Bhatia (Thesis Title: Approximation Algorithms for Scheduling Problems), PhD (August 1998). Currently at Bell Labs, NJ.
• Yoram Sussmann (Thesis Title: Approximation Algorithms for Facility Location Problems), PhD (Feb 1999). Currently at Iona College (New York).
• Rajiv Gandhi (Thesis Title: Broadcast Scheduling), PhD (May 2003). Currently at Rutgers University (Camden).
• Yoo Ah Kim (Thesis Title: Algorithms for Data Migration), PhD (June 2005). Currently at U. Connecticut.
• Justin Wan (Thesis Title: Algorithms for Data Dissemination and Collection), PhD (May 2005). Currently at Google.
• Julian Mestre (Thesis Title: Primal-Dual Algorithms for Combinatorial Optimization Problems), PhD (Aug 2007). Currently at Max Planck Institute.
• Srinivas Kashyap (Thesis Title: Algorithms for data placement, reconfiguration and monitoring in storage networks), PhD (Aug 2007). Currently at IBM T. J. Watson Research Center.

• An Zhu (Undergraduate Honors Thesis Title: A Uniform Framework for Weighted Connectivity Problems). Currently at Google.
• Srinivas Kashyap (Undergraduate Honors Thesis Title: Algorithms for Non-Uniform Size Data Placement for Parallel Disks.) Currently at University of Maryland.
• Svetlana Shargorodskaya (Undergraduate Honors Thesis Title: Implementation of Data Migration Algorithms)
• Colin Dixon (Undergraduate Honors Thesis Title: Vertex Cover Problem with Hard Capacities) Currently at University of Washington.
• Jessica Chang (Undergraduate Honors Thesis Title: Online Broadcast Scheduling: minimizing the maximum response time . Winner of the Phillip Merrill Scholarship and Honorable mention for the CRA Outstanding Undergraduate Award. Currently at University of Washington. Winner of an NSF Graduate Fellowship.

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

• Sudipto Guha PhD Stanford University, (August 2000). Currently at University of Pennsylvania.
• Abhishek Kashyap PhD, University of Maryland (Dec 2006)
• Robert Pless (Thesis Title: Video Linking), PhD (August 2000). Currently at Washington University at St. Louis.
• Suman Banerjee (Thesis Title: TBA), PhD (August 2003). Currently at Univ of Wisconsin (Madison).
• Michael Forbes. Now an undergrad at MIT. Finalist at the Intel Science Talent Search!

Current Students:

• Jian Li . Co-advised with Amol Deshpande .
• Azarakhsh Malekian .
• Matt McCutchen Finalist at the Intel Science Talent Search and Golld medalist at Informatics Olympiad!
• Barna Saha .

Projects done by other students:

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