Approximation Algorithms for Combinatorial Optimization Problems with Packing Constraints

具有填充约束的组合优化问题的近似算法

• 批准号: 399223600
• 负责人: Privatdozent Dr. Joachim Spoerhase
• 金额: --
• 依托单位: Department of Computer Science
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/399223600?language=en
• 关键词: Approximation; Algorithms; Combinatorial; Optimization; 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.

计算给定（离散）问题的最佳解决方案的任务在计算机科学中无处不在，通常称为组合优化问题。许多天然出现的问题都是NP- hard，这使得他们不太可能接受多项式时间算法将它们求解以最佳。攻击NP-HARD优化问题的一种自然方法是开发一种近似算法，该算法在多项式时间中计算一个近似值而不是最佳解决方案。近似算法的领域已导致多种算法技术。尽管该领域已经达到了一定水平的成熟度，许多有趣且基本的问题仍然开放。尤其是，目前仍然存在很大的差距，即使添加甚至（看似）简单的约束，例如容量约束（或更一般而言） ，包装约束）影响问题的近似性。对于许多基本问题（例如设施位置或K-Median），基本变体几乎是完全或至少令人满意的。许多现有的算法依赖于对问题的持续放松的密切联系。但是，这些放松在上述约束的存在下通常具有无限的完整性差距，尽管社区的巨大努力，但最著名的近似性和不合适性之间的差距很大。在该项目中，我们将研究的近似性。在包装限制的存在下，几个基本优化问题。对于其中一些问题，任何值得注意的进步都将被认为是社区的突破。在其他情况下，我们认为新的结果将是对对此类约束的存在的更系统理解的宝贵贡献。我们的重点在于研究最近开发的算法工具的功能，例如，舍入（非标准）扩展的LP公式或次次功能优化，特别是应用于这些问题。在这些问题上，我们将研究电容的位置问题，电容性或心脏性问题 - 涵盖问题的约束，网络设计问题具有距离约束（特殊的包装约束）。我们还将考虑不禁止违反限制而是在目标函数中受到惩罚的软性变体。