Live briefing
Everything about Multifit algorithm
Optimization algorithm in computer science
The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of identical-machines scheduling. It was developed by Coffman, Garey and Johnson. Its novelty comes from the fact that it uses an algorithm for another famous problem - the bin packing problem - as a subroutine. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Multifit algorithmA 5-minute orientation
- Read the landmark paper: Tighter Bounds for the Multifit Processor Scheduling AlgorithmCited 96 times
- Go sideways: Longest-processing-time-first schedulingA closely related topic
- Go sideways: First-fit-decreasing bin packingA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Tighter Bounds for the Multifit Processor Scheduling Algorithm
On the exact upper bound for the multifit processor scheduling algorithm
Evaluation of a MULTIFIT-based scheduling algorithm
The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
Multiprocessor scheduling: An extension of the MULTIFIT algorithm
Partial Solutions and MultiFit Algorithm for Multiprocessor Scheduling
The multifit algorithm for set partitioning containing kernels
Multiprocessor scheduling: An extension of the MULTIFIT algorithm
📚 Books worth reading
Open Library didn't respond; try again in a moment.
🔗 Related topics
- Longest-processing-time-first scheduling Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling. The input to the algorithm is a set of jobs, each of which has a specific…
- First-fit-decreasing bin packing First-fit-decreasing (FFD) is an algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the…
- First-fit bin packing First-fit (FF) is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items…
- Bin packing problem The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of…
- High-multiplicity bin packing High-multiplicity bin packing is a special case of the bin packing problem, in which the number of different item-sizes is small, while the number of items…
- Next-fit bin packing Next-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into…
- Best-fit bin packing Best-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into…
- Bin covering problem In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a…