Statements (48)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
mathematical optimization
|
| gptkbp:alsoKnownAs |
gptkb:bin_packing_problem
|
| gptkbp:application |
cloud computing
logistics resource allocation memory management cutting stock |
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:describes |
Given a list of items with sizes, pack them into the fewest number of bins of fixed capacity.
|
| gptkbp:estimatedCost |
Best Fit
Best Fit Decreasing First Fit First Fit Decreasing Next Fit |
| gptkbp:field |
gptkb:mathematics
computer science operations research |
| gptkbp:formedBy |
1970s
|
| gptkbp:hasAsymptoticApproximationScheme |
yes
|
| gptkbp:hasExactAlgorithm |
dynamic programming
branch and bound |
| gptkbp:hasHeuristic |
gptkb:simulated_annealing
gptkb:particle_swarm_optimization greedy algorithm metaheuristics genetic algorithm ant colony optimization tabu search |
| gptkbp:hasLowerBound |
sum of item sizes divided by bin capacity
|
| gptkbp:hasOfflineVersion |
offline bin packing
|
| gptkbp:hasPerformanceRatio |
1.7 for Best Fit Decreasing
1.7 for First Fit Decreasing 2 for Best Fit 2 for First Fit 2 for Next Fit |
| gptkbp:hasPolynomialTimeApproximationScheme |
yes
|
| gptkbp:hasUpperBound |
number of items
|
| gptkbp:hasWorstCaseApproximationRatio |
1.7
|
| https://www.w3.org/2000/01/rdf-schema#label |
one-dimensional bin packing
|
| gptkbp:referencedIn |
D.S. Johnson, 1973, 'Near-optimal bin packing algorithms'
|
| gptkbp:relatedTo |
gptkb:knapsack_problem
gptkb:cutting_stock_problem |
| gptkbp:socialMedia |
online bin packing
|
| gptkbp:studiedIn |
industrial engineering
theoretical computer science |
| gptkbp:type |
NP-hard problem
|
| gptkbp:bfsParent |
gptkb:bin_packing_problem
|
| gptkbp:bfsLayer |
8
|