Improved hardness of approximation for geometric bin packing

DOI10.1016/J.IPL.2024.106552MaRDI QIDQ7013206zbMATH OpenFDO

Authors Arka Ray, Sai Sandeep

Publication date 13 March 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106552

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A logarithmic additive integrality gap for bin packing
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Almost optimal inapproximability of multidimensional packing problems
• Approximation and online algorithms for multidimensional bin packing: a survey
• Bin packing can be solved within 1+epsilon in linear time
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Hardness of approximation for orthogonal rectangle packing and covering problems
• Improved approximation algorithm for two-dimensional bin packing
• Improved Approximation for Vector Bin Packing
• Linear degree extractors and the inapproximability of max clique and chromatic number
• New approximability results for two-dimensional bin packing
• On Multidimensional Packing Problems
• There is no APTAS for 2-dimensional vector bin packing: revisited
• There is no asymptotic PTAS for two-dimensional vector packing
• Zero knowledge and the chromatic number

This page was built for publication: Improved hardness of approximation for geometric bin packing

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