AF:Small:Beyond Worst Case Running time: Algorithms for Routing, Scheduling and Matching

Columbia University, New York NY

Investigators

Abstract

Algorithms are ubiquitous and influence many important aspects of our lives. They address decisions ranging from the mundane, e.g. which movie to watch, to the vitally important, e.g. how to manage the internet or to schedule some time-critical tasks in a navigation system. Even though computing power and network bandwidth increase at a rapid rate, users and applications increase their demand for computation and their use of networks at roughly the same pace. Thus, a critical bottleneck in many important technologies and applications is an algorithm. The problems considered in this project, mainly matching, scheduling and routing are fundamental algorithmic problems. By looking at resources such as energy, machines needed, and reassignments, the project will significantly broaden and deepen our understanding of these basic algorithmic problems. It will also design simpler algorithms that will lead to easily implementable solutions. The PI will make progress both in theory and in practice and will disseminate his results. The project will also make significant contributions to education via PI's textbook and other new materials. The PI will continue his commitment to Ph.D. student diversity. It is now well-understood that time, space and worst-case solution quality are not the only resources that need to be optimized. For the past few decades, there has been a growing emphasis on other concerns such as availability of information, use of cache, management of disk, etc. More recently, there has been a growing understanding that energy and power management are also resources that should be carefully managed. In addition, one may also be interested in features of solutions as they evolve over time, or one may be interested in the algorithm's use of resources such as machines, processing speed or updates. Finally, one may also be interested in not just the bounds that we improve, but also the real-life performance of important problems. This project plans to study several algorithmic problems that arise in scheduling, routing and matchings. The PI intends to make progress on some traditional problems and their variants and is particularly interested in considering problems from novel perspectives, that is, considering metrics that go beyond the traditionally studied ones. In particular, the project will consider energy consumption in both computers and networks, and will also consider environments in which other resources must be managed, such as minimizing the number of changes to a solution over time, the amount of processing power needed to compute a solution, or the algorithm's response to a changing environment.