• search hit 28 of 50
Back to Result List

Packing under Convex Quadratic Constraints

Submission Status:under review
  • 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 three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the golden ratio; (2) a greedy strategy; (3) a randomized rounding method leading to an approximation algorithm for the more general case with multiple convex quadratic constraints. We further show that a combination of the first two strategies 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 the three algorithms for problem instances arising in the context of real-world gas transport networks.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Max Klimm, Marc E. Pfetsch, Rico Raber, Martin Skutella
Document Type:Preprint
Language:English
Date of Publication (online):2019/11/29
Date of first Publication:2019/11/29
Release Date:2019/11/29
Institutes:Technische Universität Darmstadt
Humboldt-Universität zu Berlin
Technische Universität Berlin
Subprojects:A07
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International