There is no APTAS for 2-dimensional vector bin packing: revisited
From MaRDI portal
Publication:6072215
DOI10.1016/j.ipl.2023.106430zbMath1530.68123arXiv2104.13362OpenAlexW3158962306MaRDI QIDQ6072215
Publication date: 12 October 2023
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2104.13362
analysis of algorithmsapproximation algorithmshardness of approximationvector bin packingvector bin covering
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- There is no asymptotic PTAS for two-dimensional vector packing
- Hardness of approximation for orthogonal rectangle packing and covering problems
- Bin packing can be solved within 1+epsilon in linear time
- On-line and off-line approximation algorithms for vector covering problems
- Complexity of approximating bounded variants of optimization problems
- Approximation and online algorithms for multidimensional bin packing: a survey
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- Improved Approximation for Vector Bin Packing
- On Multidimensional Packing Problems
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items
This page was built for publication: There is no APTAS for 2-dimensional vector bin packing: revisited
