Loading [MathJax]/jax/output/SVG/config.js
Дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дискретная математика, 2017, том 29, выпуск 1, страницы 51–58
DOI: https://doi.org/10.4213/dm1405 (Mi dm1405) 		 
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

О наилучшем выборе переменной ветвления в задаче о сумме подмножеств

Р. М. Колпаковab, М. А. Посыпкинb

a МГУ им. М.В. Ломоносова
b Вычислительный центр им. А.А. Дородницына ФИЦ ИУ РАН
PDF полного текста (391 kB) Список цитирования (4)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/dm1405
Аннотация: Работа посвящена оценке вычислительной сложности метода ветвей и границ для задачи о сумме подмножеств. Исследуется влияние способа декомпозиции подзадач на число шагов метода. Рассмотрен стандартный вариант метода ветвей и границ для задачи о сумме подмножеств с бинарным ветвлением: любая подзадача разбивается на две более простые подзадачи путем присваивания выбранной переменной ветвления значений $0$ и $1$. Показано, что для любого набора параметров задачи процедура выбора в качестве переменных ветвления переменных в порядке убывания их весов является оптимальной.
Ключевые слова: метод ветвей и границ, вычислительная сложность, задача о сумме подмножеств.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-07-03102_а
Министерство образования и науки Российской Федерации НШ-8860.2016.1
Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант 15-07-03102 А), гранта поддержки ведущих научных школ РФ НШ-8860.2016.1.
Статья поступила: 31.10.2016
Англоязычная версия:
Discrete Mathematics and Applications, 2018, Volume 28, Issue 1, Pages 29–34
DOI: https://doi.org/10.1515/dma-2018-0004
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854.2
Образец цитирования: Р. М. Колпаков, М. А. Посыпкин, “О наилучшем выборе переменной ветвления в задаче о сумме подмножеств”, Дискрет. матем., 29:1 (2017), 51–58; Discrete Math. Appl., 28:1 (2018), 29–34
Цитирование в формате AMSBIB
\RBibitem{KolPos17}
\by Р.~М.~Колпаков, М.~А.~Посыпкин
\paper О наилучшем выборе переменной ветвления в задаче о сумме подмножеств
\jour Дискрет. матем.
\yr 2017
\vol 29
\issue 1
\pages 51--58
\mathnet{http://mi.mathnet.ru/dm1405}
\crossref{https://doi.org/10.4213/dm1405}
\elib{https://elibrary.ru/item.asp?id=28405135}
\transl
\jour Discrete Math. Appl.
\yr 2018
\vol 28
\issue 1
\pages 29--34
\crossref{https://doi.org/10.1515/dma-2018-0004}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000425893900004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85054968824}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm1405
  • https://doi.org/10.4213/dm1405
  • https://www.mathnet.ru/rus/dm/v29/i1/p51
    • Эта публикация цитируется в следующих 4 статьяx:
    1. V. Cacchiani, M. Iori, A. Locatelli, S. Martello, “Knapsack problems — An overview of recent advances. Part I: Single knapsack problems”, Computers & Operations Research, 143 (2022), 105692  crossref  mathscinet
    2. Р. М. Колпаков, “Оптимальная стратегия решения частного случая задачи о ранце методом ветвей и границ”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2021, № 3, 13–22  mathnet  mathscinet  zmath; R. M. Kolpakov, “Optimal strategy for solving a special case of the knapsack problem by the branch and bound method”, Moscow University Mathematics Bulletin, 76:3 (2021), 97–106  crossref  isi
    3. Hu Zhiyuan, Hu Wenqian, Li Xiang, Ma Zhi, Wang Wenli, Wang Xudong, Li Chunyang, Huang Tiancong, “Research on wide area industrial internet scheduling algorithm based on service reachability”, J. Electron. Inf. Technol., 43:9 (2021), 2608–2616  crossref  isi
    4. Р. М. Колпаков, М. А. Посыпкин, “Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ”, Дискрет. матем., 31:4 (2019), 20–37  mathnet  crossref  mathscinet; R. M. Kolpakov, M. A. Posypkin, “Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method”, Discrete Math. Appl., 30:5 (2020), 313–325  crossref  isi  elib
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Статистика просмотров:
    Страница аннотации:2180
    PDF полного текста:80
    Список литературы:88
    Первая страница:36
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025