Three-Bar Charts Packing Problem

DOI10.1007/978-3-031-22990-9_5MaRDI QIDQ6090762zbMATH OpenOpenAlexFDO

Authors A. I. Erzin

Publication date 17 November 2023

Published in Communications in Computer and Information Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-22990-9_5

zbMATH Keywords

approximationbar chartsStrip packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Applications of mathematical programming (90C90)

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
• An improved approximation for packing big two-bar charts
• Two-bar charts packing problem
• A posteriori analysis of the algorithms for two-bar charts packing problem

Cites work

• 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 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
• An -approximation algorithm for the asymmetric maximum TSP
• 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 3639144 (Why is no real title available?)
• Improved Approximation for Vector Bin Packing
• Optimal investment in the development of oil and gas field
• 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)

• A 4/3 OPT+2/3 approximation for big two-bar charts packing problem
• An improved approximation for packing big two-bar charts
• Updated estimates for algorithms for packing 2-bar charts in a strip

This page was built for publication: Three-Bar Charts Packing Problem

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