Sistemy i Sredstva Informatiki [Systems and Means of Informatics]
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sistemy i Sredstva Inform.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sistemy i Sredstva Informatiki [Systems and Means of Informatics], 2023, Volume 33, Issue 3, Pages 61–75
DOI: https://doi.org/10.14357/08696527230305
(Mi ssi896)
 

This article is cited in 1 scientific paper (total in 1 paper)

Efficiency of the reduction algorithms in the bin packing problem

E. B. Barashova, A. V. Egorkinb, D. V. Lemtyuzhnikovaac, M. A. Posypkind

a V. A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, 65 Profsoyuznaya Str., Moscow 117997, Russian Federation
b National Research University of Electronic Technology (MIET), 1 Shokina Sq., Moscow, Zelenograd 124498, Russian Federation
c Moscow State Aviation Institute (National Research University), 4 Volokolamskoe Shosse, Moscow 125933, Russian Federation
d Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119133, Russian Federation
Full-text PDF (545 kB) Citations (1)
References:
Abstract: The bin packing problem is a well-known combinatorial problem consisting in finding the minimum number of fixed-size bins to hold a given set of items with known weight. Despite its simple formulation, the problem is NP-hard and exact methods for its solution are often inefficient in practice. Therefore, the research and development of approximate methods for solving the bin packing problem is of great importance. The paper investigates a class of approximate algorithms consisting of the sequential application of reduction and one of four “greedy” algorithms. The effect of reduction on the quality of the solutions obtained and the running time of the methods under consideration is evaluated. The algorithms are compared on four data sets according to several criteria responsible for the quality of the obtained solutions and the time required to find them. The experimental study shows that the efficiency of the reduction varies widely and depends strongly on the problem coefficients.
Keywords: reduction, bin-packing problem, discrete optimization, greedy algorithms, solution improvement by two-sided placement.
Funding agency Grant number
Russian Science Foundation 22-71-10131
This research is partially supported by the Russian Science Foundation (project No. 22-71-10131).
Received: 02.02.2023
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: E. B. Barashov, A. V. Egorkin, D. V. Lemtyuzhnikova, M. A. Posypkin, “Efficiency of the reduction algorithms in the bin packing problem”, Sistemy i Sredstva Inform., 33:3 (2023), 61–75
Citation in format AMSBIB
\Bibitem{BarEgoLem23}
\by E.~B.~Barashov, A.~V.~Egorkin, D.~V.~Lemtyuzhnikova, M.~A.~Posypkin
\paper Efficiency of the~reduction algorithms in~the~bin packing problem
\jour Sistemy i Sredstva Inform.
\yr 2023
\vol 33
\issue 3
\pages 61--75
\mathnet{http://mi.mathnet.ru/ssi896}
\crossref{https://doi.org/10.14357/08696527230305}
\edn{https://elibrary.ru/QDUAMY}
Linking options:
  • https://www.mathnet.ru/eng/ssi896
  • https://www.mathnet.ru/eng/ssi/v33/i3/p61
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Системы и средства информатики
    Statistics & downloads:
    Abstract page:72
    Full-text PDF :28
    References:18
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024