Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
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


Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find




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

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2006, Volume 46, Number 12, Pages 2289–2304 (Mi zvmmf374)  
This article is cited in 8 scientific papers (total in 8 papers)

Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

M. A. Posypkina, I. Kh. Sigalb

a Institute of System Analysis, Russian Academy of Sciences, pr. Shestidesyatiletiya Oktyabrya 9, Moscow, 117312, Russia
b Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119991, Russia
Full-text PDF (2432 kB) Citations (8)
Abstract: The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.
Key words: algorithms for parallel computations, discrete optimization, branch-and-bound method, speedup estimate, model of the computation process.
Received: 09.02.2006
English version:
Computational Mathematics and Mathematical Physics, 2006, Volume 46, Issue 12, Pages 2187–2202
DOI: https://doi.org/10.1134/S0965542506120165
Bibliographic databases:
Document Type: Article
UDC: 519.854
Language: Russian
Citation: M. A. Posypkin, I. Kh. Sigal, “Speedup estimates for some variants of the parallel implementations of the branch-and-bound method”, Zh. Vychisl. Mat. Mat. Fiz., 46:12 (2006), 2289–2304; Comput. Math. Math. Phys., 46:12 (2006), 2187–2202
Citation in format AMSBIB
\Bibitem{PosSig06}
\by M.~A.~Posypkin, I.~Kh.~Sigal
\paper Speedup estimates for some variants of the parallel implementations of the branch-and-bound method
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2006
\vol 46
\issue 12
\pages 2289--2304
\mathnet{http://mi.mathnet.ru/zvmmf374}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2344973}
\transl
\jour Comput. Math. Math. Phys.
\yr 2006
\vol 46
\issue 12
\pages 2187--2202
\crossref{https://doi.org/10.1134/S0965542506120165}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33846183271}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf374
  • https://www.mathnet.ru/eng/zvmmf/v46/i12/p2289
    • This publication is cited in the following 8 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024