Packing under convex quadratic constraints

DOI10.1007/S10107-021-01675-6MaRDI QIDQ2118134zbMATH OpenOpenAlexFDO

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

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-021-01675-6

zbMATH Keywords

binary packing problemconstant-factor approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Packing under convex quadratic constraints
• Inverse convex programming and parallelepiped packing
• Geometric Packing under Nonuniform Constraints
• Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization
• Geometric packing under non-uniform constraints
• scientific article; zbMATH DE number 480248
• Bin packing under linear constraints
• Optimized packings with applications
• On Multidimensional Packing Problems
• scientific article; zbMATH DE number 1305407

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 1933860 (Why is no real title available?)
• Knapsack auctions
• Manipulation of Voting Schemes: A General Result
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• On the complexity of approximating \(k\)-dimensional matching
• Optimal Auction Design
• Packing under convex quadratic constraints
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• 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

(7)

• Inverse convex programming and parallelepiped packing
• 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?)
• Packing under convex quadratic constraints
• 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 Q2118134)