Approximation Algorithms for Combinatorial Optimization Problems with Packing Constraints

计算给定(离散)问题的最优解的任务在计算机科学中是普遍存在的，通常被称为组合优化问题。自然产生的许多问题都是NP难的，这使得它们不太可能采用多项式时间算法来解决它们的最优。解决NP-Hard优化问题的一种自然方法是开发一种近似算法，该算法在多项式时间内计算近似解而不是最优解。近似算法领域产生了过多的算法技术。虽然这个领域已经达到了一定的成熟程度，但许多有趣的基本问题仍然悬而未决。特别是，目前在理解添加即使是一个(看起来)简单的约束(或更广泛地说，包装约束)如何影响问题的逼近性方面仍存在很大差距。对于许多基本问题(如设施选址或k-中位数)，基本变量几乎完全或至少令人满意地被理解。现有的许多算法都依赖于与问题的不断松弛有密切联系。然而，在上述约束的存在下，这些松弛往往具有无限的完整性差距，而且尽管社会上做出了巨大的努力，但最已知的可逼近界和不可逼近界之间的差距很大。在这个项目中，我们将研究几个基本优化问题在填充约束下的可逼近性。对于其中一些问题，任何值得注意的进展都将被视为社区的突破。在其他情况下，我们认为，新的成果将有助于更系统地了解这些制约因素的存在。我们的重点是研究最近发展起来的算法工具，例如舍入(非标准)扩展LP公式或子模函数优化应用于这些问题时的能力，特别是研究容量约束的选址问题、容量或基数约束的覆盖问题、具有距离约束的网络设计问题(一种特殊的布局约束)。我们还将考虑软约束变体，其中违反约束并不是被禁止的，而是在目标函数中受到惩罚。

The task of computing an optimal solution to a given (discrete) problem is ubiquitous in computer science and is usually referred to as an combinatorial optimization problem. Many of the naturally arising problems are NP-hard, which makes it unlikely that they admit a polynomial time algorithm solving them to optimality. A natural way to attack NP-hard optimization problems is to develop an approximation algorithm that computes in polynomial time an approximate rather than an optimal solution. The field of approximation algorithms has lead to a plethora of algorithmic techniques. And although this field has already reached a certain level of maturity many interesting and fundamental questions remain open.In particular, there is currently still big gap in understanding how adding even a (seemingly) simple constraint such as a capacity constraint (or, more generally, packing constraints) affects the approximability of the problem. For many fundamental problems (such as facility location or k-median) the basic variant is understood almost completely or at least satisfactorily. Many existing algorithms rely on a close connection to a continuous relaxation of the problem. However, these relaxations often have an unbounded integrality gap under the presence of the above-mentioned constraints and also the gap between the best known approximability and inapproximability bounds are large despite significant efforts by the community.In this project, we will study the approximability of several fundamental optimization problems under the presence of packing constraints. For some of these problems any noteworthy progress would be considered a breakthrough in the community. In other cases, we believe that new results would be a valuable contribution to a more systematic understanding of the presence of such constraints. Our focus lies in investigating the power of recently developed algorithmic tools, for example, rounding (non-standard) extended LP formulations or submodular function optimization, when applied to these problems.In particular, we will study capacitated location problems, capacitated or cardinality-constrained covering problems, network design problems with distance constraints (a special packing constraint). We will also consider soft-constrained variants where violating the constraints is not forbidden but penalized in the objective function.