Improved approximation for two-dimensional vector multiple knapsack

DOI10.1016/j.comgeo.2024.102124MaRDI QIDQ6639376

Tomer Cohen, Hadas Shachnai, Ariel Kulik

Publication date: 15 November 2024

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmrandomized roundingconfiguration-LPmultiple \textsc{knapsack}

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• There is no asymptotic PTAS for two-dimensional vector packing
• Approximation schemes for generalized two-dimensional vector packing with application to data placement
• There is no EPTAS for two-dimensional knapsack
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Model and algorithms for multi-period sea cargo mix problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Very large-scale neighborhood search for the \(K\)-constraint multiple knapsack problem
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Parameterized Approximation Scheme for the Multiple Knapsack Problem
• A sharp concentration inequality with applications
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• There is no APTAS for 2-dimensional vector bin packing: revisited
• Tight vector bin packing with few small items via fast exact matching in multigraphs

This page was built for publication: Improved approximation for two-dimensional vector multiple knapsack