My research focuses on the design and analysis of approximation algorithms for combinatorially difficult optimization problems. The essential nature of these problems precludes the development of acceptably fast (i.e. polynomial time) algorithms that produce optimal solutions. Such combinatorially difficult problems arise with a very high frequency in computer science and engineering, including many aspects of network design, such as scheduling and routing, protocol design, and schemes for network configuration.

Unfortunately, simply knowing that a fast algorithm producing optimal solutions is not possible, does not make the problem go away. It is important to know what alternatives exist. Investigating those alternatives is the basis for my research. My work has most often focused on the development of fast approximation algorithms to solve these combinatorially difficult problems. That is, to develop fast algorithms that, while not producing optimal solutions, will produce solutions that are provably close to optimal. Often, it can also be shown experimentally that these near optimal solutions will work as well in practice as optimal ones.

My research into approximation algorithms involves four interrelated threads. First, there is algorithm design - we want to design an algorithm that produces an approximate solution. Second, we want to analyze the performance of that algorithm in terms of the approximate solution it produces - just how close to optimal is that approximate solution (obviously, the closer to optimal, the better)? Third, we are concerned with the running time of the algorithm. Finally, we want to run a series of experiments/simulations with the algorithm to study both its running time and the quality of its approximations "in practice". Obviously, these four threads are highly interdependent. Usually, the trick is find an algorithm that is fast, produces a good solution, and yet is simple enough to allow analysis.

My most recent work has focused on extending the study of approximation algorithms in the direction of accommodating dynamic changes in the problem instance. That is, in situations where the problem instance is not provided all in "one piece", but rather, over time, pieces of the instance may arrive and depart. The goal is to develop algorithms that can accept changes in the instance (arrivals or departures of pieces of the instance) and can recompute a good approximate solution in significantly less time than if the approximate solution was simply fully recomputed every time a change occurs.

Attacking these problems is difficult since they involve an extra dimension - not only do we consider the approximation aspect, but we also need to consider the fully dynamic aspect. Our work on these problems has been focussed in two domains: 1) bin packing and 2) network optimization. At present the majority of my work is concentrated on these problems in the networking domain.

For detailed information see my papers in various areas available from my publications via my main web page.