Packing under convex quadratic constraints

DOI10.1007/978-3-030-45771-6_21MaRDI QIDQ5041751zbMATH OpenOpenAlexFDO

Authors Max Klimm, Marc E. Pfetsch, Rico Raber, Martin Skutella

Publication date 14 October 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.00468

zbMATH Keywords

binary packing problemconvex quadratic knapsack constraint

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

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 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 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.

Recommendations

• Packing under convex quadratic constraints
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Maximum generalized assignment with convex costs
• Bin packing under linear constraints
• Approximation and Online Algorithms

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• Approximate Algorithms for the 0/1 Knapsack Problem
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Approximation of the quadratic knapsack problem
• Approximation techniques for utilitarian mechanism design
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Cotenancy and competition in an experimental auction market for natural gas pipeline networks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• Knapsack auctions
• Manipulation of Voting Schemes: A General Result
• Optimal Auction Design
• Packing under convex quadratic constraints
• Quadratic knapsack problems
• Reducibility among combinatorial problems
• Speed scaling to manage energy and temperature
• The polynomial solvability of convex quadratic programming
• The quadratic 0-1 knapsack problem with series-parallel support
• Truthful approximation mechanisms for restricted combinatorial auctions
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(8)

• Inverse convex programming and parallelepiped packing
• A PTAS for a class of binary non-linear programs with low-rank functions
• Packing under convex quadratic constraints
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Valid constraints for the Point Packing in a Square problem
• Geometric Packing under Nonuniform Constraints
• scientific article; zbMATH DE number 1830743 (Why is no real title available?)
• Higher‐Dimensional Packing with Order Constraints

Describes a project that uses

Uses Software

• GasLib

This page was built for publication: Packing under convex quadratic constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041751)