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
Artikel, Zweitveröffentlichung, Verlagsversion
 | Es ist eine neuere Version dieses Eintrags verfügbar. |
Kurzbeschreibung (Abstract)
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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2024 |
| Autor(en): | Klimm, Max ; Pfetsch, Marc E. ; Raber, Rico ; Skutella, Martin |
| Art des Eintrags: | Zweitveröffentlichung |
| Titel: | Packing under convex quadratic constraints |
| Sprache: | Englisch |
| Publikationsjahr: | 19 März 2024 |
| Ort: | Darmstadt |
| Publikationsdatum der Erstveröffentlichung: | März 2022 |
| Ort der Erstveröffentlichung: | Berlin ; Heidelberg |
| Verlag: | Springer |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Mathematical Programming: Series A, Series B |
| Jahrgang/Volume einer Zeitschrift: | 192 |
| (Heft-)Nummer: | 1-2 |
| DOI: | 10.26083/tuprints-00023454 |
| URL / URN: | https://tuprints.ulb.tu-darmstadt.de/23454 |
| Zugehörige Links: | |
| Herkunft: | Zweitveröffentlichung DeepGreen |
| Kurzbeschreibung (Abstract): | 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: | Verlagsversion |
| URN: | urn:nbn:de:tuda-tuprints-234544 |
| Zusätzliche Informationen: | Mathematics Subject Classification: 90C27, 90C35, 68Q25 Special Issue: Integer Programming and Combinatorial Optimization (IPCO) 2020 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Fachbereich(e)/-gebiet(e): | 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung |
| Hinterlegungsdatum: | 19 Mär 2024 13:51 |
| Letzte Änderung: | 28 Mär 2024 08:51 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
Verfügbare Versionen dieses Eintrags
- Packing under convex quadratic constraints. (deposited 19 Mär 2024 13:51) [Gegenwärtig angezeigt]
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum