Saturday 19 July 2014

Discrete Geometry - Bin Packing Problem

This post is a little irrelevant to general contents of my blog, but I found this to be a interesting geometry problem and it does have some ties with Computational Geometry, which is form a of theoretical computer science. There is additionally some connection with Computational Complexity Theory too. The Bin Packing Problem isn't difficult to explain, and yet can be difficult to find a optimal solution.

With Discrete Mathematics, I personally find that the branches within this field are more accessible but the problems are difficult enough to be interesting and form a field of serious mathematical study. I'm only a amateur mathematician and a student, so if there are any problems then please highlight them in the comments section.

Bin Packing Problem:

The Bin Packing Problem is an example of a optimization problem which has a surprisingly large number of applications, especially in logistics and data management. The Bin Packing Problem asks to minimize the number of bins needed to pack a certain number and given volume for a list of objects. These objects can vary in size, but the bin volumes will remain fixed. There are some programs which will give valid suggestions for the most optimal method, however, the problem is a NP- Hard Combinatorial class type.

The sum of the sizes of the items must be less than or equal to the total volume of the bins being used. The size of the items can never be greater than the total volume of the bins. If the volume of one bin is reached, then a new bin will need to be used. The problem looks to find a packing method which will reduce the number of bins needed to provide a optimal method.

The First-Fit Algorithm is the best algorithm which has been used for the bin packing problem. The First-Fit Algorithm is an example of a greedy approximation algorithm, in that the items will processed in any given order. The algorithm will place as many items as possible into the first bin, and then create a new bin if no other additional bins can be found. The process is then repeated for the rest of the items.

The First-Fit Algorithm has a approximation factor of 2 (APX). The approximation factor is used for NP-Hard problems, since it is very unlikely that a efficient algorithm will be produced to solve the problem directly, and therefore a P class algorithm can be developed in order to find a approximate answer. The approximation factor of 2, means that the algorithm will never use more than twice the number of least bins needed for the bin packing problem. For instance, if the number of bins needed was 2, then the algorithm will never use more than 4.

References:

Bin Packing Problem


8 comments:

  1. I think the admin of this site is really working hard for his site, for the reason that here every information is quality based
    information.



    스포츠토토
    메이저사이트 목록
    먹튀검증

    ReplyDelete
  2. Normally I do not learn article on blogs, however I wish to say that this write-up very pressured me to take a look at and do so! Your writing style has been surprised me. Thank you, quite great article.



    스포츠토토티비
    스포츠중계
    토토사이트

    ReplyDelete
  3. Taking Assignment Helpin qatar student assignment, they can timely submit their assignment. Students need not worry about the assignment deadline. Our support team best service provide the other company.

    ReplyDelete

  4. Before searching ecology research topics ,you should know about what is ecology?It is focused on how living organism interect with sourrounds.It is one of the very interesting subject for environment students. When we talk about finding super topic then we have to hustle and all.




    ReplyDelete
  5. Myassignmenthelp.co.uk is the best assignment help service provider in UK with most of the 5000+ qualified writers. Provide academic help in different courses like, assignments help, coursework help, homework help, dissertation help, essay help , case study help, thesis help, course code help, online exam help etc. Some are listed below:

    Assignment Writing service
    help with an assignment
    Write My paper
    Coursework Writing service
    Erp Assignment help

    ReplyDelete
  6.  Are you tired of getting bad grades on your assignments? Pay someone to do my assignment is the solution. Here you get all the help you need. College students, Ph.D and MBA degree holders working in various companies can handle your work effectively. All our experts are specially trained for writing payment assignment help, and all of them have enough experience in their fields of study, so that they can fulfill your requirements easily and quickly

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete