A 71/60 theorem for bin packing
From MaRDI portal
Publication:1083194
DOI10.1016/0885-064X(85)90022-6zbMath0604.68046OpenAlexW2004690405WikidataQ56212221 ScholiaQ56212221MaRDI QIDQ1083194
Michael R. Garey, David S. Johnson
Publication date: 1985
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0885-064x(85)90022-6
Related Items
An improved two-machine flowshop scheduling with intermediate transportation, Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time, Machine Scheduling with a Maintenance Interval and Job Delivery Coordination, A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem, Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems, A survey on combinatorial optimization in dynamic environments, Online algorithms for 1-space bounded multidimensional bin packing and hypercube packing, Worst-case analysis of fast heuristics for packing squares into a square, A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm, Single-machine scheduling with periodic maintenance to minimize makespan revisited, Three-Bar Charts Packing Problem, A study on load-balanced variants of the bin 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, Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing, Machine scheduling with a maintenance interval and job delivery coordination, A variant of multi-task \(n\)-vehicle exploration problem: maximizing every processor's average profit, A fast asymptotic approximation scheme for bin packing with rejection, A 3/2-approximation for big two-bar charts packing, Two-bar charts packing problem, On lazy bin covering and packing problems, Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A storage-size selection problem
- Probabilistic analysis for simple one- and two-dimensional bin packing algorithms
- Analysis and design of algorithms in combinatorial optimization. (School held in Udine in September 1979)
- Bin packing can be solved within 1+epsilon in linear time
- The ellipsoid method and its consequences in combinatorial optimization
- A Linear Programming Approach to the Cutting-Stock Problem
- A new proof for the first-fit decreasing bin-packing algorithm
- New Algorithms for Bin Packing
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- A Linear Programming Approach to the Cutting Stock Problem—Part II
