CAREER: Approximation Algorithms for Graph-Theoretic Problems

职业：图论问题的近似算法

• 批准号: 9501355
• 负责人: Samir Khuller
• 金额: $ 12.28万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-09-01 至 1999-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9501355&HistoricalAwards=false
• 关键词: CAREER; Approximation; Algorithms; Graph; Theoretic

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.

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