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

DOI10.1007/S10958-023-06319-YarXiv2212.00944OpenAlexW4323045613MaRDI QIDQ6147752FDOQ6147752

Author name not available (Why is that?)

Publication date: 1 February 2024

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

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.

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A 71/60 theorem for bin packing
• Bin packing can be solved within 1+epsilon in linear time
• A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
• Complex Scheduling
• Resource constrained scheduling as generalized bin packing
• There is no asymptotic PTAS for two-dimensional vector packing
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• 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 new proof for the first-fit decreasing bin-packing algorithm
• Approximation and online algorithms for multidimensional bin packing: a survey
• The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
• A 3/2-approximation for big two-bar charts packing
• Two-bar charts packing problem
• Optimal Investment in the Development of Oil and Gas Field
• A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem
• An improved approximation for packing big two-bar charts

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)