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

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

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.