TU Darmstadt / ULB / TUprints

Packing under convex quadratic constraints

Klimm, Max ; Pfetsch, Marc E. ; Raber, Rico ; Skutella, Martin (2024)
Packing under convex quadratic constraints.
In: Mathematical Programming: Series A, Series B, 2022, 192 (1-2)
doi: 10.26083/tuprints-00023454
Article, Secondary publication, Publisher's Version

[img] Text
Copyright Information: CC BY 4.0 International - Creative Commons, Attribution.

Download (569kB)
Item Type: Article
Type of entry: Secondary publication
Title: Packing under convex quadratic constraints
Language: English
Date: 19 March 2024
Place of Publication: Darmstadt
Year of primary publication: March 2022
Place of primary publication: Berlin ; Heidelberg
Publisher: Springer
Journal or Publication Title: Mathematical Programming: Series A, Series B
Volume of the journal: 192
Issue Number: 1-2
DOI: 10.26083/tuprints-00023454
Corresponding Links:
Origin: Secondary publication DeepGreen

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.

Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-234544
Additional Information:

Mathematics Subject Classification: 90C27, 90C35, 68Q25

Special Issue: Integer Programming and Combinatorial Optimization (IPCO) 2020

Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics > Optimization
Date Deposited: 19 Mar 2024 13:51
Last Modified: 30 Apr 2024 07:09
SWORD Depositor: Deep Green
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/23454
PPN: 517330091
Actions (login required)
View Item View Item