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

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

• 批准号: 1161365
• 负责人: Mohammad Hajiaghayi
• 金额: $ 20万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1161365&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 的目标是开发近似和固定参数算法的通用框架。