A. Zehmakan. International Journal on Foundations of Computer Science & Technology (IJFCST), 5 (4):
11(July 2015)
DOI: 10.5121/ijfcst.2015.5401
Abstract
The Bin Packing Problem is one of the most important optimization problems. In recent years, due to its
NP-hard nature, several approximation algorithms have been presented. It is proved that the best
algorithm for the Bin Packing Problem has the approximation ratio 3/2 and the time orderO(n),
unlessP=NP. In this paper, first, a
-approximation algorithm is presented, then a modification to FFD
algorithm is proposed to decrease time order to linear. Finally, these suggested approximation algorithms
are compared with some other approximation algorithms. The experimental results show the suggested
algorithms perform efficiently.
In summary, the main goal of the research is presenting methods which not only enjoy the best theoretical
criteria, but also perform considerably efficient in practice.
%0 Journal Article
%1 noauthororeditor
%A Zehmakan, AbdolahadNoori
%D 2015
%J International Journal on Foundations of Computer Science & Technology (IJFCST)
%K Bin Decreasing FFD FirstFit Packing Problem algorithm approximation ratio
%N 4
%P 11
%R 10.5121/ijfcst.2015.5401
%T BIN PACKING PROBLEM: TWO APPROXIMATION
ALGORITHMS
%U https://wireilla.com/papers/ijfcst/V5N4/5415ijfcst01.pdf
%V 5
%X The Bin Packing Problem is one of the most important optimization problems. In recent years, due to its
NP-hard nature, several approximation algorithms have been presented. It is proved that the best
algorithm for the Bin Packing Problem has the approximation ratio 3/2 and the time orderO(n),
unlessP=NP. In this paper, first, a
-approximation algorithm is presented, then a modification to FFD
algorithm is proposed to decrease time order to linear. Finally, these suggested approximation algorithms
are compared with some other approximation algorithms. The experimental results show the suggested
algorithms perform efficiently.
In summary, the main goal of the research is presenting methods which not only enjoy the best theoretical
criteria, but also perform considerably efficient in practice.
@article{noauthororeditor,
abstract = {The Bin Packing Problem is one of the most important optimization problems. In recent years, due to its
NP-hard nature, several approximation algorithms have been presented. It is proved that the best
algorithm for the Bin Packing Problem has the approximation ratio 3/2 and the time orderO(n),
unlessP=NP. In this paper, first, a
-approximation algorithm is presented, then a modification to FFD
algorithm is proposed to decrease time order to linear. Finally, these suggested approximation algorithms
are compared with some other approximation algorithms. The experimental results show the suggested
algorithms perform efficiently.
In summary, the main goal of the research is presenting methods which not only enjoy the best theoretical
criteria, but also perform considerably efficient in practice. },
added-at = {2023-07-20T08:00:26.000+0200},
author = {Zehmakan, AbdolahadNoori},
biburl = {https://www.bibsonomy.org/bibtex/250c35fe6c21f8b0db1242bba8e35aa96/devino},
doi = {10.5121/ijfcst.2015.5401},
interhash = {c8b62d240b3cb6a0c5f7fd8e757ee534},
intrahash = {50c35fe6c21f8b0db1242bba8e35aa96},
issn = {ISSN : 1839-7662},
journal = {International Journal on Foundations of Computer Science & Technology (IJFCST)},
keywords = {Bin Decreasing FFD FirstFit Packing Problem algorithm approximation ratio},
language = {ENGLISH},
month = jul,
number = 4,
pages = 11,
timestamp = {2023-07-20T08:00:26.000+0200},
title = {BIN PACKING PROBLEM: TWO APPROXIMATION
ALGORITHMS},
url = {https://wireilla.com/papers/ijfcst/V5N4/5415ijfcst01.pdf},
volume = 5,
year = 2015
}