CAREER: Approximation Algorithms for Graph-Theoretic Problems

图形是强大的工具，可用于对对象和对象之间的关系进行建模。事实上，许多不同的问题可以用图论的术语表示为优化问题。具体地说，图论提供了一种很好的方法来对与交通、网络设计、调度、机器人和许多其他领域相关的问题进行建模。它被用来开发和说明不同算法工具的功能。本提案中考虑的特定问题可以从三个大的方面抽象出来：(1)网络设计：如何构建连接给定站点集的网络？如何使网络变得可靠，并在站点之间提供高带宽(同时保持低成本)？这样的基本问题在这里得到了阐述。(2)运动规划：代理如何在环境中导航？什么是在未知环境中导航的好导航策略？在这种情况下，代理通过实际接触障碍物来发现环境。当在有限的内存下工作时，代理如何记录环境的近似地图？(3)调度：基于优先级的调度问题出现在并行机的制造和编译环境中。如何为这类问题设计有效的启发式方法？对于这些问题中的大多数，即使是在多项式时间内也很难获得近似解。教育计划：大多数计算机科学家经常面临设计算法来解决问题的任务。尽管这些出现在许多不同的环境中，但一些基本原则是设计有效的算法和数据结构的基础。作为这一职业奖项教育计划的一部分，PI正在计划：(A)承担学生设计算法的培训，以及(B)教他们重新检查现有算法的重要性，以使其更简单和更有效。算法实验室是朝着这个方向迈出的重要一步，学生在这里承担项目，实施算法，并担任其他研究小组中学生的顾问。

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.