Statements (65)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Combinatorial Optimization Problem
|
| gptkbp:alsoKnownAs |
gptkb:Bin_Packing_Problem
|
| gptkbp:application |
gptkb:Logistics
Scheduling Resource Allocation Memory Management |
| gptkbp:approximationRatio |
1.7 (First Fit Decreasing)
1.22 (Best Known Polynomial Time) |
| gptkbp:complexity |
NP-complete
|
| gptkbp:decision |
Given n items and k bins, can all items be packed into k bins?
|
| gptkbp:describes |
The bin packing problem is to pack objects of different volumes into a finite number of bins or containers in a way that minimizes the number of bins used.
|
| gptkbp:field |
Computer Science
Operations Research |
| gptkbp:formedBy |
1970
|
| gptkbp:generalizes |
Variable-sized Bin Packing
Multidimensional Bin Packing |
| gptkbp:hasSpecialCase |
gptkb:Partition_Problem
gptkb:Cutting_Stock_Problem gptkb:Set_Cover_Problem gptkb:Subset_Sum_Problem Offline Bin Packing One-dimensional Bin Packing Online Bin Packing Bin Covering Circle Packing Generalized Assignment Problem Multidimensional Knapsack Problem Multiple Knapsack Problem Multiway Assignment Problem Multiway Bin Packing Problem Multiway Covering Problem Multiway Cut Problem Multiway Matching Problem Multiway Number Partitioning Multiway Packing Problem Multiway Partition Problem Multiway Partitioning Problem Multiway Resource Allocation Problem Multiway Scheduling Problem Strip Packing Vector Packing |
| gptkbp:hasSubgroup |
Resource Allocation Problems
Packing Problems |
| gptkbp:hasVariant |
Online Bin Packing
Variable-sized Bin Packing Bin Covering Multidimensional Bin Packing |
| https://www.w3.org/2000/01/rdf-schema#label |
Bin Packing
|
| gptkbp:input |
A list of item sizes and bin capacity
|
| gptkbp:NP-hard |
Yes
|
| gptkbp:objective |
Minimize the number of bins used
|
| gptkbp:output |
Assignment of items to bins
|
| gptkbp:relatedTo |
gptkb:Knapsack_Problem
gptkb:Partition_Problem gptkb:Cutting_Stock_Problem |
| gptkbp:supportsAlgorithm |
Approximation Algorithms
Exact Algorithms Best Fit Best Fit Decreasing First Fit First Fit Decreasing Next Fit Worst Fit |
| gptkbp:bfsParent |
gptkb:Online_Load_Balancing
|
| gptkbp:bfsLayer |
7
|