Graphs are powerful tools that can be used to model objects and relationships between objects. Indeed, many distinct problems can be cast as optimization problems in graph theoretic terms. Specifically, graph theory provides an excellent way to model problems related to transportation, network design, scheduling, robotics and many other areas. It is used to develop and illustrate the power of different algorithmic tools. There are three broad areas from which the particular problems considered in this proposal are abstracted: (1) Network Design: How can a network that connects a given set of sites be built? How can the network be made reliable, and also provide high bandwidth between sites (while keeping the cost low)? Such fundamental questions are addressed here. (2) Motion Planning: How does an agent navigate in an environment? What are good navigation strategies for navigating in unknown environments? In this case the agent discovers the environment by actually touching obstacles. How does an agent record an approximate map of the environment, when working with limited memory? (3) Scheduling: Precedence based scheduling problems arise in the context of manufacturing and compilation for parallel machines. How can effective heuristics for such problems be designed? For most of these problems it is very difficult to obtain even an approximate solution in polynomial time. Education Plan: Most computer scientists are constantly faced with the task of designing algorithms to solve problems. Although these arise in many different contexts, some basic principles underlie the design of efficient algorithms and data structures. As a part of the Education Program of this CAREER award, the PI is planning: (a) to undertake the training of students in designing algorithms, and (b) to teach them the importance of re-examining existing algorithms so as to make them simpler and more efficient. An algorithms lab where students undertake projects, implement algorithms, and act as consultants to students in other research groups is a significant step in this direction.
