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.