Approximation Algorithms for Combinatorial Optimization Problems with Packing Constraints

计算给定（离散）问题的最优解的任务在计算机科学中无处不在，通常被称为组合优化问题。许多自然产生的问题是NP难的，这使得它们不太可能允许多项式时间算法将其解决为最优。解决NP难优化问题的一种自然方法是开发一种近似算法，该算法在多项式时间内计算近似解而不是最优解。近似算法领域已经导致了过多的算法技术。虽然这个领域已经达到了一定的成熟度，但许多有趣的基本问题仍然没有解决。特别是，目前在理解如何添加（看似）简单的约束（如容量约束（或更一般地，包装约束））影响问题的可逼近性方面仍然存在很大的差距。对于许多基本问题（如设施位置或k-中位数），基本变量几乎完全或至少令人满意地理解。许多现有的算法依赖于一个密切的连接到一个连续的放松的问题。然而，这些松弛往往有一个无界的完整性差距的存在下，上述的约束，也差距之间的最佳已知的逼近和不可逼近的界限是巨大的，尽管显着的努力community.In这个项目中，我们将研究几个基本的优化问题的逼近下存在的包装约束。对于其中一些问题，任何值得注意的进展都会被认为是社区的突破。在其他情况下，我们认为，新的结果将有助于更系统地了解这种制约因素的存在。我们的重点在于调查最近开发的算法工具的力量，例如，舍入（非标准）扩展LP配方或次模函数优化，当应用于这些problems.特别是，我们将研究容量限制的位置问题，容量限制或基数约束的覆盖问题，网络设计问题的距离约束（一个特殊的包装约束）。我们还将考虑软约束变体，其中不禁止违反约束，但会在目标函数中受到惩罚。

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.