Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
From MaRDI portal
Publication:392175
DOI10.1016/j.tcs.2013.09.007zbMath1359.90116OpenAlexW179790402MaRDI QIDQ392175
Zsolt Tuza, Xin Han, Rongheng Li, György Dósa
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.007
Related Items (24)
Single machine scheduling with job delivery to multiple customers ⋮ Minmizing service span with batch-position-based learning effects ⋮ Scheduling with interjob communication on parallel processors ⋮ An introduction to stochastic bin packing-based server consolidation with conflicts ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ Non-resumable scheduling on a single bounded parallel-batch machine with periodic maintenance ⋮ Batched bin packing revisited ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A variable neighborhood search approach to solve the order batching problem with heterogeneous pick devices ⋮ Open-end bin packing: new and old analysis approaches ⋮ Compact integer linear programming formulations for the temporal bin packing problem with fire-ups ⋮ Mathematical models and approximate solution approaches for the stochastic bin packing problem ⋮ Bin packing under linear constraints ⋮ Scheduling with Interjob Communication on Parallel Processors ⋮ Integrated scheduling on a batch machine to minimize production, inventory and distribution costs ⋮ PARALLEL MACHINE SCHEDULING WITH JOB DELIVERY COORDINATION ⋮ Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms ⋮ Scheduling with job delivery coordination on single machine ⋮ Max-min bin packing algorithm and its application in nano-particles filling ⋮ Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Two parallel machines scheduling with two-vehicle job delivery to minimize makespan ⋮ A tight approximation algorithm for problem \(P2\rightarrow D|v=1,c=1|C_{\max }\) ⋮ Several methods of analysis for cardinality constrained bin packing
Cites Work
- On the machine scheduling problem with job delivery coordination
- 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 tighter bound for FFd algorithm
- 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
This page was built for publication: Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
