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.