Tight approximation algorithms for geometric bin packing with skewed items

DOI10.1007/s00453-023-01116-0arXiv2105.02827OpenAlexW3157982676MaRDI QIDQ6053472

Arindam Khan, Eklavya Sharma

Publication date: 27 September 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsguillotine cutsgeometric bin packing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Hardness of approximation for orthogonal rectangle packing and covering problems
• Bin packing can be solved within 1+epsilon in linear time
• The two-dimensional cutting stock problem revisited
• Approximation and online algorithms for multidimensional bin packing: a survey
• Smart-Grid Electricity Allocation via Strip Packing with Slicing
• Iterative Methods in Combinatorial Optimization
• On strip packing With rotations
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• On Packing Two-Dimensional Bins
• Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
• New Finite Pivoting Rules for the Simplex Method
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Improved Approximation for Vector Bin Packing
• A Logarithmic Additive Integrality Gap for Bin Packing
• Approximating Geometric Knapsack via L-packings
• A (5/3 + ε)-Approximation for Strip Packing
• Approximation Schemes for Independent Set and Sparse Subsets of Polygons
• Multistage Cutting Stock Problems of Two and More Dimensions
• Cutting glass
• Improved Approximation Algorithm for Two-Dimensional Bin Packing
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Packing d-Dimensional Bins in d Stages
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• New Approximability Results for Two-Dimensional Bin Packing
• Linear programming. Foundations and extensions
• Algorithms and Computation
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• On Guillotine Separability of Squares and Rectangles.
• Approximation Algorithms for Demand Strip Packing
• Peak Demand Minimization via Sliced Strip Packing.

This page was built for publication: Tight approximation algorithms for geometric bin packing with skewed items