Аннотация:
Статья посвящена вопросам сложности решения задачи об одномерном булевом ранце методом ветвей и границ. Для рассматриваемой сложности получены две верхние оценки. Выделен частный случай задачи о ранце, когда сложность ее решения полиномиально ограничена размерностью задачи. Получены также верхняя и нижняя оценки сложности решения методом ветвей и границ задачи о сумме подмножеств, являющейся частным случаем задачи о ранце.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05-01-00495a, 06-07-89079a.
Образец цитирования:
Р. М. Колпаков, М. А. Посыпкин, “Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце”, Дискрет. матем., 22:1 (2010), 58–73; Discrete Math. Appl., 20:1 (2010), 95–112
\RBibitem{KolPos10}
\by Р.~М.~Колпаков, М.~А.~Посыпкин
\paper Верхняя и нижняя оценки трудоемкости метода ветвей и~границ для задачи о~ранце
\jour Дискрет. матем.
\yr 2010
\vol 22
\issue 1
\pages 58--73
\mathnet{http://mi.mathnet.ru/dm1084}
\crossref{https://doi.org/10.4213/dm1084}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2675431}
\zmath{https://zbmath.org/?q=an:05779535}
\elib{https://elibrary.ru/item.asp?id=20730324}
\transl
\jour Discrete Math. Appl.
\yr 2010
\vol 20
\issue 1
\pages 95--112
\crossref{https://doi.org/10.1515/DMA.2010.006}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1084
https://doi.org/10.4213/dm1084
https://www.mathnet.ru/rus/dm/v22/i1/p58
Эта публикация цитируется в следующих 13 статьяx:
Saurabh Mishra, Sonia Khetarpaul, “uR-tree: a spatial index structure for handling multiple point selection queries”, Multimed Tools Appl, 82:6 (2023), 8093
Jinhui Dai, Junkun Yan, Wenqiang Pu, Hongwei Liu, Maria Sabrina Greco, “Adaptive Channel Assignment for Maneuvering Target Tracking in Multistatic Passive Radar”, IEEE Trans. Aerosp. Electron. Syst., 59:3 (2023), 2780
Jie Li, Cong Zhang, Zhi Liu, Richang Hong, Han Hu, “Optimal Volumetric Video Streaming With Hybrid Saliency Based Tiling”, IEEE Trans. Multimedia, 25 (2023), 2939
Р. М. Колпаков, “Оптимальная стратегия решения частного случая задачи о ранце методом ветвей и границ”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2021, № 3, 13–22; 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
Sin Si Thu Thant, “The Parallel Processing Approach to the Dynamic Programming Algorithm of Knapsack Problem”, Proceedings of the 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (Elconrus), IEEE Nw Russia Young Researchers in Electrical and Electronic Engineering Conference, IEEE, 2021, 2252–2256
Kolpakov R., Posypkin M., “The Scalability Analysis of a Parallel Tree Search Algorithm”, Optim. Lett., 14:8 (2020), 2211–2226
Kolpakov R., Posypkin M., “Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem”, Open Comput. Sci., 11:1 (2020), 116–126
Р. М. Колпаков, М. А. Посыпкин, “Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ”, Дискрет. матем., 31:4 (2019), 20–37; 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
Dolgui A., Gafarov E., “Can a Branch and Bound Algorithm Solve All Instances of Salbp-1 Efficiently?”, IFAC PAPERSONLINE, 52:13 (2019), 2788–2791
Р. М. Колпаков, М. А. Посыпкин, “О наилучшем выборе переменной ветвления в задаче о сумме подмножеств”, Дискрет. матем., 29:1 (2017), 51–58; R. M. Kolpakov, M. A. Posypkin, “On the best choice of a branching variable in the subset sum problem”, Discrete Math. Appl., 28:1 (2018), 29–34
А. Ю. Попков, Б. С. Дарховский, Ю. С. Попков, “Итерационный МК-алгоритм решения задач глобальной оптимизации”, Автомат. и телемех., 2017, № 2, 82–98; A. Yu. Popkov, B. S. Darkhovsky, Yu. S. Popkov, “Iterative MC-algorithm to solve the global optimization problems”, Autom. Remote Control, 78:2 (2017), 261–275
Р. М. Колпаков, М. А. Посыпкин, Си Ту Тант Син, “Сложность решения задачи о сумме подмножеств методом ветвей и границ с доминированием и мощностным отсевом”, Автомат. и телемех., 2017, № 3, 96–110; 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”, Autom. Remote Control, 78:3 (2017), 463–474
Kolpakov R., Posypkin M., “The Lower Bound on Complexity of Parallel Branch-and-Bound Algorithm For Subset Sum Problem”, Numerical Computations: Theory and Algorithms (Numta-2016), AIP Conference Proceedings, 1776, eds. Sergeyev Y., Kvasov D., DellAccio F., Mukhametzhanov M., Amer Inst Physics, 2016, 050008
Цитирование в формате AMSBIB
Обратная связь: