A Linear Approximation Algorithm for 2-Dimensional Vector Packing

We study the 2-dimensional vector packing problem, which is a generalization of the classical bin packing problem where each item has 2 distinct weights and each bin has 2 corresponding capacities. The goal is to group items into minimum number of bins, without violating the bin capacity constraints...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-03
Main Authors: Otoo, Ekow, Ali, Pinar, Rotem, Doron
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Mathematical analysis
Operations research
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the 2-dimensional vector packing problem, which is a generalization of the classical bin packing problem where each item has 2 distinct weights and each bin has 2 corresponding capacities. The goal is to group items into minimum number of bins, without violating the bin capacity constraints. We propose a \Theta}(n)-time approximation algorithm that is inspired by the O(n^2) algorithm proposed by Chang, Hwang, and Park.
ISSN:2331-8422