Packing under convex quadratic constraints

• 成果类型: Article
• 署名作者: Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
• 署名单位: Technical University of Berlin; Technical University of Darmstadt
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01675-6
• 发表日期: 2022
• 页码: 361-386
• 关键词: approximation algorithms; Knapsack

摘要

We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.