Improved approximation bounds for Vector Bin Packing

Details Improved approximation bounds for Vector Bin Packing Improved approximation bounds for Vector Bin Packing

2010-07-08

arxiv.org/abs/1007.1345v1

Computer Science

Data Structures and Algorithms

15 pages, 3 algorithms

Scientific paper

In this paper we propose an improved approximation scheme for the Vector Bin Packing problem (VBP), based on the combination of (near-)optimal solution of the Linear Programming (LP) relaxation and a greedy (modified first-fit) heuristic. The Vector Bin Packing problem of higher dimension (d \geq 2) is not known to have asymptotic polynomial-time approximation schemes (unless P = NP). Our algorithm improves over the previously-known guarantee of (ln d + 1 + epsilon) by Bansal et al. [1] for higher dimensions (d > 2). We provide a {\theta}(1) approximation scheme for certain set of inputs for any dimension d. More precisely, we provide a 2-OPT algorithm, a result which is irrespective of the number of dimensions d.

Affiliated with

Also associated with

No associations

Rating

Improved approximation bounds for Vector Bin Packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved approximation bounds for Vector Bin Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved approximation bounds for Vector Bin Packing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-102833