Avtomatika i Telemekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






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


Avtomatika i Telemekhanika, 2017, Issue 3, Pages 96–110 (Mi at14415)  

This article is cited in 4 scientific papers (total in 4 papers)

System Analysis and Operations Research

Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering

R. M. Kolpakovab, M. A. Posypkinb, Si Tu Tant Sinc

a Moscow State University, Moscow, Russia
b Dorodnicyn Computing Centre, Russian Academy of Sciences, Moscow, Russia
c Moscow Institute of Electronic Equipment, Moscow, Russia
Full-text PDF (651 kB) Citations (4)
References:
Abstract: We obtain an exact upper bound on the complexity of solving the Subset Sum problem with a variation of the branch-and-bound method of a special form. Complexity is defined as the number of subproblems considered in the process of solving the original problem. Here we reduce the enumeration by using the domination relation. We construct an instance of the Subset Sum problem on which our bound is realized. The resulting bound is asymptotically twice smaller than the exact upper bound on the complexity of solving this problem with a standard version of the branch-and-bound method.
Keywords: knapsack problem, branch-and-bound method, computational complexity, domination relation.
Funding agency Grant number
Russian Foundation for Basic Research 15-07-03102 А
Ministry of Education and Science of the Russian Federation НШ-8860.2016.1
This work was supported by the Russian Foundation for Basic Research, project no. 15-07-03102a and the Program of State Support for Leading Scientific Schools, project no. NSH-8860.2016.1.
Presented by the member of Editorial Board: A. A. Lazarev

Received: 05.04.2016
Accepted: 30.06.2016
English version:
Automation and Remote Control, 2017, Volume 78, Issue 3, Pages 463–474
DOI: https://doi.org/10.1134/S0005117917030079
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: R. M. Kolpakov, M. A. Posypkin, Si Tu Tant Sin, “Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering”, Avtomat. i Telemekh., 2017, no. 3, 96–110; Autom. Remote Control, 78:3 (2017), 463–474
Citation in format AMSBIB
\Bibitem{KolPosSin17}
\by R.~M.~Kolpakov, M.~A.~Posypkin, Si~Tu~Tant~Sin
\paper Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering
\jour Avtomat. i Telemekh.
\yr 2017
\issue 3
\pages 96--110
\mathnet{http://mi.mathnet.ru/at14415}
\elib{https://elibrary.ru/item.asp?id=28960581}
\transl
\jour Autom. Remote Control
\yr 2017
\vol 78
\issue 3
\pages 463--474
\crossref{https://doi.org/10.1134/S0005117917030079}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000396338200007}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014880774}
Linking options:
  • https://www.mathnet.ru/eng/at14415
  • https://www.mathnet.ru/eng/at/y2017/i3/p96
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Avtomatika i Telemekhanika
    Statistics & downloads:
    Abstract page:261
    Full-text PDF :124
    References:49
    First page:16
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024