AF: Small: Approximation Techniques for Combinatorial Optimization

近似技术在组合优化问题的算法设计中很有价值。数学规划松弛提供了难优化问题的易于处理的版本，这对设计好的算法很有用——在某些情况下，这些松弛和它们的对偶可以作为算法设计和下界证明的指南。这种近似技术不仅对传统的优化问题有用，而且对在线算法和其他领域的问题也很有用。该项目提出研究近似技术发挥关键作用的各种问题-其中许多问题是关于近似算法中的基本问题，但许多问题是关于数学松弛和其他近似技术的见解发挥重要作用的问题。这个项目的广泛目标包括：(a)更好地理解在优化问题上使用lift-and-project松弛，比如着色问题，以及为低阈值秩的图开发算法技术的密切相关问题，(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.