one-dimensional bin packing

URI: https://gptkb.org/entity/one-dimensional_bin_packing
GPTKB entity
Statements (48)
Predicate Object
gptkbp:instanceOf gptkb: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
gptkb:genetic_algorithm
greedy algorithm
metaheuristics
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
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 gptkb:theoretical_computer_science
industrial engineering
gptkbp:type gptkb:NP-hard_problem
gptkbp:bfsParent gptkb:bin_packing_problem
gptkbp:bfsLayer 8
https://www.w3.org/2000/01/rdf-schema#label one-dimensional bin packing