Flexible and Effective Techniques for the Design of Approximation Algorithms

离散优化问题在日常生活中比比皆是，每当需要对稀缺资源进行有效分配的复杂决策时，离散优化问题就会出现。这样的问题太多了，包括在本地交通网络中列车的及时调度，以及在现代芯片的VLSI设计阶段的导线的最佳布局。在这两个例子中，相关的实际情况通常是np困难的，因此难以处理。这一建议的重点是设计的近似算法，有效地计算近最优解给定的优化问题。重点将放在系统地使用数学规划（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.