AF: Small: Approximation Techniques for Combinatorial Optimization

逼近技术在组合优化问题的算法设计中是很有价值的。数学编程松弛提供了在设计好的算法时有用的困难优化问题的易处理版本--在某些情况下，这些松弛及其对偶用作算法设计和下限证明的指南。这种近似技术不仅在传统的优化问题中有用，而且在在线算法和其他领域的问题中也是有用的。这个项目建议研究各种近似技术发挥关键作用的问题--这些问题中有许多是关于近似算法中的基本问题，但也有许多是关于从数学放松和其他近似技术中获得的见解发挥重要作用的问题。这个项目的主要目标包括：(A)更好地了解提升和投影松弛在优化问题(如着色)中的使用，以及为低门槛秩图开发算法技术的密切相关问题，(B)试图弥合我们对经典优化问题(如旅行商问题和装箱问题)的理解差距，以及(C)揭示较新的问题，如加权匹配的在线版本和新的流公式。优化问题是无处不在的，对于许多感兴趣的问题，我们有强有力的证据表明，不可能获得精确有效的解。为了避免这种困难，我们设计了有效的启发式算法，它不一定能找到最优解，但可以保证它们产生的解不会远离最优解(即近似最优解)。数学规划是设计这类近似算法的一个非常重要的工具。成功地实现项目目标将需要我们在这一领域的知识方面取得进展，特别是对强大和多功能的数学编程工具包的新见解。作为该项目的一部分，研究生和本科生将通过让他们参与这些研究活动来进行培训。研究生和本科课程的课程材料将根据这一项目的研究成果以及该领域的新发展而编制。

Approximation techniques are valuable in the design of algorithms for combinatorial optimization problems. Mathematical programming relaxations provide tractable versions of hard optimization problems that are useful in the design of good algorithms -- in some cases, these relaxations and their duals serve as a guide for the design of algorithms and lower bound proofs. Such approximation techniques are useful not just in traditional optimization problems, but also for problems in online algorithms and other areas. This project proposes to study a variety of problems where approximation techniques play a crucial role -- many of these questions are about basic problems in approximation algorithms, but many are about questions where insights from mathematical relaxations and other approximation techniques play an important role. The broad goals of this project include (a) Obtaining a better understanding of the use of lift-and-project relaxations for optimization problems like coloring and the closely related question of developing algorithmic techniques for graphs of low threshold rank, (b) Attempting to close gaps in our understanding of classical optimization problems like the traveling salesman problem and bin packing, and (c) Shedding light on newer problems like online versions of weighted matching and new flow formulations.Optimization problems are ubiquitous and for many such problems of interest, we have strong evidence that it is impossible to obtain exact efficient solutions. To circumvent this intractability, we design efficient heuristics that may not find the best solution necessarily, but have guarantees that the solution they produce is not far from the optimal (i.e. is approximately optimal). Mathematical programming is a very important tool in designing such approximation algorithms. Successfully achieving the project goals will require advances in our knowledge of this area, and especially new insights into the powerful and versatile mathematical programming toolkit. As part of this project, graduate and undergraduate students will be trained by involving them in these research activities. Course materials for graduate and undergraduate courses will be developed distilling research results of this project, as well as new developments in the field.