Flexible and Effective Techniques for the Design of Approximation Algorithms

灵活有效的逼近算法设计技术

• 批准号: 288340-2012
• 负责人: Könemann, Jochen
• 金额: $ 3.06万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=571398
• 关键词: Flexible; Effective; Techniques; Design; Approximation

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.

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