A Linear Approximation Algorithm for 2-Dimensional Vector Packing

摘要: We study the 2-dimensional vector packing problem, which is a generalization of classical bin problem where each item has 2 distinct weights and corresponding capacities. The goal to group items into minimum number bins, without violating capacity constraints. propose \Theta}(n)-time approximation algorithm that inspired by O(n^2) proposed Chang, Hwang, Park.