A 3/2-approximation for big two-bar charts packing
From MaRDI portal
Publication:2045041
DOI10.1007/s10878-021-00741-1zbMath1473.90137arXiv2006.10361OpenAlexW3154267549MaRDI QIDQ2045041
Roman Plotnikov, Georgii Melidi, Stepan Nazarenko, Adil I. Erzin
Publication date: 11 August 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.10361
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (4)
A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ Three-Bar Charts Packing Problem ⋮ A 4/3 OPT+2/3 approximation for big two-bar charts packing problem ⋮ An improved approximation for packing big two-bar charts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Experimental investigation of heuristics for resource-constrained project scheduling: an update
- A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing
- A 71/60 theorem for bin packing
- 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
- The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
- A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
- Two-bar charts packing problem
- Genetic algorithm for the resource-constrained project scheduling problem
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
- A new proof for the first-fit decreasing bin-packing algorithm
- Efficient algorithms for finding maximum matching in graphs
- A self-adapting genetic algorithm for project scheduling under resource constraints
- Optimal Investment in the Development of Oil and Gas Field
This page was built for publication: A 3/2-approximation for big two-bar charts packing
