Flexible and Effective Techniques for the Design of Approximation Algorithms

离散优化问题在日常生活中大量存在，每当需要做出关于稀缺资源有效分配的复杂决策时，就会出现离散优化问题。这样的问题有很多，包括本地交通网络中列车的及时调度，以及现代芯片的VLSI设计阶段的最佳布线。在这两个例子中，一般来说，相关的实际例子往往是NP难的，因此难以处理。这一建议侧重于设计能够有效地计算给定优化问题的近最优解的近似算法。重点将放在这类算法的设计中系统地使用数学规划(MP)。 MP是开发近似算法的重要工具。从一个问题的数学模型出发，一个人通常首先得到一个强大而容易处理的松弛，然后解决它，并最终将其解四舍五入为对原始问题可行的解。这种算法的性能比主要取决于两个主要因素：MP松弛的质量和舍入方法。虽然在过去的30年里已经开发了几种用于上述舍入过程的强大的通用方法，但以下元问题(转译自Vazirani的书)仍然存在：给定强大的MP松弛，是否总是有方法将其舍入为基础优化问题的良好解决方案？阐明这个问题是我研究的长期目标。更明确地说，在我的研究计划中，我打算系统地研究强MP松弛在近似算法设计中的使用。我举了三个正在进行的项目的例子，以及几个短期目标的例子。拟议的研究目标是组合优化和理论计算机科学的核心；所取得的进展预计将对这些领域和MP的实际应用产生重大的直接影响。拟议的研究计划是现有工作的自然延续，它将继续吸引优秀的学生。

Discrete optimization problems are abundant in everyday life, and arise whenever complex decisions about the efficient distribution of scarce resources have to be made. There is a plethora of such problems, including the timely scheduling of trains in a local transit network, and the optimal layout of wires in the VLSI design phase of a modern chip. In these two examples, and in general, relevant practical instances are often NP-hard, and thus intractable. This proposal focuses on the design of Approximation Algorithms that efficiently compute near-optimal solutions to given optimization problems. Emphasis will be placed on the systematic use of mathematical programming (MP) in the design of such algorithms. MP is an important tool in the development of approximation algorithms. Starting from a mathematical model of a problem, one typically first derives a strong and tractable relaxation, solves it, and ultimately rounds its solution into one that is feasible for the original problem. The performance ratio of such an algorithm chiefly depends on two main factors: the quality of the MP relaxation, and the rounding method. While several powerful and general purpose methods for the above rounding process have been developed in the last 30 years, the following meta question (paraphrased from Vazirani's book) remains: Given a strong MP relaxation, is there always a way of rounding it into a good solution for the underlying optimization problem? Shedding light on this question is the long-term goal of my research. More explicitly, in my research program I intend to systematically study the use of strong MP relaxations in the design of approximation algorithms. I give three examples of ongoing projects together with several example short-term goals. The proposed research objectives are central in Combinatorial Optimization and Theoretical Computer Science; progress made is anticipated to have significant direct impact in these fields, and in practical applications of MP. The proposed research program is a natural continuation of existing work, and it will continue to attract excellent students.