AF: Medium: Collaborative Research: General Frameworks for Approximation and Fixed-Parameter Algorithms

AF：媒介：协作研究：近似和固定参数算法的通用框架

• 批准号: 1161626
• 负责人: Erik Demaine
• 金额: $ 40万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1161626&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; General

This research develops general frameworks for efficient graph algorithms, which allow to solve entire categories of computational problems all at once. The PIs aim for a general theory of algorithms, wherein a given problem of interest can simply be adapted into the general approach. This approach differs from the traditional study of algorithms, which often focuses on individual solutions to specific problems.The type of computational graph problems the PIs consider are "optimization problems", where the task is to find a solution whose cost, quality, size, profit, energy, or speed is as large or as small as possible. Most interesting graph optimization problems are NP-hard, essentially implying that there are no efficient algorithms to find the very best solution. This research considers the two main types of algorithms for solving NP-hard graph optimization problems. Approximation algorithms allow the result to be a small factor away from the optimal, but still require a fast running time. Fixed-parameter algorithms allow the running time to be exponential, but confine that exponentiality to a (typically small) parameter other than the problem size, while requiring an optimal solution.The type of graphs the PIs consider include planar graphs, which can be drawn in two dimensions without any edges crossing each other, and nearly planar graphs such as graphs of bounded genus and graphs excluding a fixed minor. Many graphs of practical interest---for example, computer networks and road networks, which are "drawn" on Earth---are planar or nearly planar. In these settings, the PIs aim to develop general frameworks for approximation and fixed-parameter algorithms.

这项研究开发了高效图算法的通用框架，可以一次解决整个类别的计算问题。 PI的目标是算法的一般理论，其中给定的感兴趣的问题可以简单地适应一般的方法。 这种方法与传统的算法研究不同，传统的算法研究通常侧重于特定问题的个体解决方案。PI考虑的计算图问题类型是“优化问题”，其中的任务是找到一个解决方案，其成本，质量，规模，利润，能量或速度尽可能大或尽可能小。 大多数有趣的图优化问题都是NP难的，本质上意味着没有有效的算法来找到最佳解决方案。 本研究考虑了解决NP难图优化问题的两种主要类型的算法。 近似算法允许结果与最优值相差很小，但仍然需要快速的运行时间。 固定参数算法允许运行时间是指数的，但将指数限制在一个（通常很小的）参数而不是问题大小，同时需要一个最优解。PI考虑的图形类型包括平面图，可以在二维中绘制，没有任何边相互交叉，以及几乎平面的图形，如有界亏格的图形和不包括固定子图的图形。 许多有实际意义的图-例如，计算机网络和道路网络，它们是在地球上“画”出来的-是平面或近似平面的。 在这些设置中，PI旨在为近似和固定参数算法开发通用框架。