A 4/3 OPT+2/3 approximation for big two-bar charts packing problem

DOI10.1007/S10958-023-06319-YMaRDI QIDQ6147752zbMATH OpenOpenAlexFDO

Authors

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/2212.00944

Mathematics Subject Classification ID

Theory of computing (68Qxx) Mathematical programming (90Cxx)

Abstract: Two-Bar Charts Packing Problem is to pack $n$ two-bar charts (2-BCs) in a minimal number of unit-capacity bins. This problem generalizes the strongly NP-hard Bin Packing Problem. We prove that the problem remains strongly NP-hard even if each 2-BC has at least one bar higher than 1/2. Next we consider the case when the first (or second) bar of each 2-BC is higher than 1/2 and show that the $O(n^2)$-time greedy algorithm with preliminary lexicographic ordering of 2-BCs constructs a packing of length at most $OPT+1$, where $OPT$ is optimum. Eventually, this result allowed us to present an $O(n^{2.5})$-time algorithm that constructs a packing of length at most $4/3cdotOPT+2/3$ for the NP-hard case when each 2-BC has at least one bar higher than 1/2.

Recommendations

• An improved approximation for packing big two-bar charts
• 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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 3/2-approximation for big two-bar charts packing
• A 71/60 theorem for bin packing
• A new proof for the first-fit decreasing bin-packing algorithm
• A posteriori analysis of the algorithms for two-bar charts packing problem
• A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) 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
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• An improved approximation for packing big two-bar charts
• Approximation and online algorithms for multidimensional bin packing: a survey
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Bin packing can be solved within 1+epsilon in linear time
• Complex Scheduling
• Optimal investment in the development of oil and gas field
• Resource constrained scheduling as generalized bin packing
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
• There is no asymptotic PTAS for two-dimensional vector packing
• Two-bar charts packing problem

Cited in

(3)

• Three-Bar Charts Packing Problem
• An improved approximation for packing big two-bar charts
• Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem

This page was built for publication: A 4/3 OPT+2/3 approximation for big two-bar charts packing problem

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