CRII: AF: On Designing Approximation Algorithms Based on Round-or-Cut Paradigm

许多离散优化问题在实践中出现的是棘手的，近似算法框架提供了有效的算法，这些优化问题的解决方案的质量可证明的保证。其中，线性规划（LP）技术在近似算法领域发挥了核心作用。 该项目旨在了解这种技术的力量，通过利用一个非常灵活的范例设计基于LP的算法，称为“圆形或切割”的范例。 PI的目标是使用这种范式来解决许多组合优化问题，这些问题似乎很难以其他方式解决。 成功地完成这个项目不仅会产生这些问题的改进的近似算法，而且会导致更好地理解线性规划技术的力量。作为该项目的一部分，本科生和研究生将接受培训并参与研究活动。这个研究项目的课程材料将在网上免费提供。最近，圆形或切割范式导致了许多改进的近似算法。 该范例不同于传统的“松弛和轮”范例，因为用于近似问题的LP松弛不需要是有效可解的。 因此，舍入或切割范例具有灵活性，舍入算法可以自适应地选择要求分数解满足的线性约束的集合。该项目的主要目标是利用这种灵活性来解决使用传统松弛和舍入范式似乎很难解决的问题，包括容量限制的k中值问题，相同机器上的机器最小化问题以及路径上的不可分割流问题。 第二个目标是理解“不圆就切”范式和传统的“松弛圆”范式之间的差距。到目前为止，在设计LP近似算法时，松弛-舍入范式远比舍入-切割范式更流行。仅对于少数问题，算法需要更强的圆形或切割范式。PI将调查松弛和圆形范例是否足以解决这些问题。

Numerous discrete optimization problems arising in practice are intractable; the approximation algorithms framework provides efficient algorithms for these optimization problems with provable guarantees on the quality of solutions. Among many others, the linear programming (LP) technique has played a central role in the area of approximation algorithms. This project seeks to understand the power of this technique, by exploiting a very flexible paradigm in designing LP-based algorithms, called the "round-or-cut" paradigm. The PI aims to use this paradigm to tackle many combinatorial optimizations problems that seem hard to tackle in other ways. Successful completion of the project will not only yield improved approximation algorithms for these problems, but also lead to a better understanding of the power of linear programming technique. As a part of the project, undergraduate and graduate students will be trained and involved in the research activities. The course materials resulting from this research project will be made freely accessible online.Recently, the round-or-cut paradigm has led to many improved approximation algorithms. This paradigm differs from the traditional "relax-and-round" paradigm in that the LP relaxation used to approximate the problem does not need to be efficiently solvable. As a result, the round-or-cut paradigm has the flexibility that the rounding algorithm can adaptively choose the set of linear constraints to require the fractional solution to satisfy. The major goal of this project is to leverage this flexibility to tackle problems that seem hard to tackle using the traditional relax-and-round paradigm, including the capacitated k-median problem, the machine minimization problem on identical machines, and the unsplittable flow problem on paths. The second goal is to understand the gap between the round-or-cut paradigm and the traditional relax-and-round paradigm. So far, the relax-and-round paradigm is far more popular than the round-or-cut paradigm in designing LP-based approximation algorithms. For a few problems only, algorithms require the stronger round-or-cut paradigm. The PI will investigate whether the relax-and-round paradigm is sufficient for these problems.