An improved approximation for packing big two-bar charts

DOI10.1007/S10958-022-06151-WMaRDI QIDQ6187994zbMATH OpenOpenAlexFDO

Authors A. I. Erzin, V. V. Shenmaier

Publication date 1 February 2024

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Recently, we presented a new Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generalization of the Bin Packing Problem and 2-D Vector Packing Problem. Earlier, we have proposed several polynomial approximation algorithms. In particular, when each 2-BC has at least one bar of height more than 1/2, we have proposed a 3/2--approximation polynomial algorithm. This paper proposes an $O(n^3)$--time 16/11--approximation algorithm for packing 2-BCs when at least one bar of each BC has a height not less than 1/2 and an $O(n^{2.5})$--time 5/4--approximation algorithm for packing non-increasing or non-decreasing 2-BCs when each 2-BC has at least one bar which height is more than 1/2, where $n$ is the number of 2-BCs.

Recommendations

• A 4/3 OPT+2/3 approximation for big two-bar charts packing problem
• A 3/2-approximation for big two-bar charts packing
• Three-Bar Charts Packing Problem
• Two-bar charts packing problem
• A posteriori analysis of the algorithms for two-bar charts packing problem

Cites work

• A 2.5 times optimal algorithm for packing in two dimensions
• A 3/2-approximation for big two-bar charts packing
• A 71/60 theorem for bin packing
• A (5/3+)-approximation for strip packing
• A branch-and-price algorithm for the two-dimensional vector packing problem
• A new proof for the first-fit decreasing bin-packing algorithm
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Improved Approximation for Vector Bin Packing
• Optimal investment in the development of oil and gas field
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• Two-bar charts packing problem

Cited in

(3)

• Three-Bar Charts Packing Problem
• Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem
• A 4/3 OPT+2/3 approximation for big two-bar charts packing problem

This page was built for publication: An improved approximation for packing big two-bar charts

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