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.