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

点击翻译按钮获取中文摘要

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.