<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>287</id>
    <completedYear>2019</completedYear>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>preprint</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>2019-11-29</completedDate>
    <publishedDate>2019-11-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Packing under Convex Quadratic Constraints</title>
    <abstract language="eng">We consider a general class of binary packing problems with a convex quadratic knapsack constraint.&#13;
We prove that these problems are APX-hard to approximate and present constant-factor approximation&#13;
algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored&#13;
to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the&#13;
golden ratio; (2) a greedy strategy; (3) a randomized rounding method&#13;
leading to an approximation algorithm for the more general case with multiple convex quadratic&#13;
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&#13;
algorithms for problem instances arising in the context of real-world gas transport networks.</abstract>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="review.accepted_by">2</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Max Klimm</author>
    <author>Marc E. Pfetsch</author>
    <author>Rico Raber</author>
    <author>Martin Skutella</author>
    <collection role="institutes" number="">Technische Universität Darmstadt</collection>
    <collection role="institutes" number="">Humboldt-Universität zu Berlin</collection>
    <collection role="institutes" number="">Technische Universität Berlin</collection>
    <collection role="subprojects" number="">A07</collection>
    <file>https://opus4.kobv.de/opus4-trr154/files/287/packing_convex_quadratic.pdf</file>
  </doc>
</export-example>
