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. 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.