Flexible and Effective Techniques for the Design of Approximation Algorithms

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

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.