Statements (52)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Combinatorial Optimization Problem
|
| gptkbp:application |
gptkb:Logistics
gptkb:Cutting_Stock_Problem Resource Allocation Memory Management |
| gptkbp:approximationAlgorithm |
Best Fit
Best Fit Decreasing First Fit First Fit Decreasing Next Fit |
| gptkbp:approximationRatio |
1.7 (First Fit Decreasing)
|
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:exactAlgorithm |
gptkb:Dynamic_Programming
gptkb:Branch_and_Bound |
| gptkbp:field |
gptkb:Mathematics
Computer Science Operations Research |
| gptkbp:firstDescribed |
1970s
|
| gptkbp:generalizes |
Multi-dimensional Bin Packing
One-dimensional Bin Packing |
| gptkbp:goal |
Minimize number of bins used
|
| https://www.w3.org/2000/01/rdf-schema#label |
Bin Packing Problem
|
| gptkbp:relatedTo |
gptkb:Knapsack_Problem
gptkb:Partition_Problem gptkb:Set_Cover_Problem |
| gptkbp:typicalInput |
Bin capacity
List of items with sizes |
| gptkbp:usedIn |
Manufacturing
Telecommunications Cloud Computing Scheduling Data Storage Network Design Parallel Processing Cargo Loading Resource Scheduling Server Consolidation Memory Allocation Container Scheduling Cutting Stock Packing Industry Task Assignment Virtual Machine Placement |
| gptkbp:variant |
Bin Packing with Cardinality Constraints
Bin Packing with Conflicts Multi-dimensional Bin Packing Offline Bin Packing Online Bin Packing Variable-sized Bin Packing |
| gptkbp:bfsParent |
gptkb:Knapsack_Problem
gptkb:Cutting_Stock_Problem |
| gptkbp:bfsLayer |
7
|