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


Avtomat. i Telemekh., 2017, Issue 3, Pages 96–110 (Mi at14415)  

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

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

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.

Author to whom correspondence should be addressed

Full text: PDF file (651 kB)
References: PDF file   HTML file

English version:
Automation and Remote Control, 2017, 78:3, 463–474

Bibliographic databases:

Presented by the member of Editorial Board: . . 

Received: 05.04.2016
Accepted: 30.06.2016

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{http://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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000396338200007}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014880774}


Linking options:
  • http://mi.mathnet.ru/eng/at14415
  • http://mi.mathnet.ru/eng/at/y2017/i3/p96

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. X. Ji, Ya. Li, Y. Yu, Sh. Fan, “Optimal dispatching and game analysis of power grid considering demand response and pumped storage”, Syst. Sci. Control Eng., 6:3, SI (2018), 270–277  crossref  isi  scopus
  • Avtomatika i Telemekhanika
    Number of views:
    This page:123
    Full text:5
    References:14
    First page:16

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020