А.А. Дородницына ФИЦ ИУ РАН, Москва), М.А. ПОСЫПКИН, д-р физ.-мат. наук (mposypkin@gmail.com) (Вычислительный центр им. <...> А.А. Дородницына ФИЦ ИУ РАН, Москва), СИ ТУ ТАНТ СИН (Московский институт электронной техники) СЛОЖНОСТЬ РЕШЕНИЯ ЗАДАЧИ О СУММЕ ПОДМНОЖЕСТВ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ С ДОМИНИРОВАНИЕМ И МОЩНОСТНЫМ ОТСЕВОМ1 Получена точная верхняя оценка сложности решения задачи о сумме подмножеств вариантом метода ветвей и границ специального вида. <...> Cложность определяется как число рассматриваемых в процессе решения задачи подзадач. <...> При этом применяется сокращение перебора за счет использования отношения доминирования. <...> Построен пример задачи о сумме подмножеств, на котором полученная оценка достигается. <...> Полученная оценка асимптотически в 2 раза меньше точной верхней оценки сложности решения этой задачи стандартным вариантом метода ветвей и границ. <...> Ключевые слова: задача о ранце, метод ветвей и границ, вычислительная сложность, отношение доминирования. <...> Введение В работе рассматривается задача о сумме подмножеств, которая является частным случаем задачи о ранце с одним ограничением, при котором веса и стоимости предметов совпадают. <...> Предполагается, что коэффициенты C, wi, i =1,. ,n, данной задачи являются натуральными числами иn i=1wi C. <...> Один из современных подходов к 1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 15-07-03102 А), гранта поддержки ведущих научных школ РФ НШ-8860.2016.1. <...> 96 i=1 n wixi →max, wixi C, решению задачи о ранце — так называемый графический метод, предложенный А.А. Лазаревым [3]. <...> Суть метода состоит в сокращении перебора за счет удаления доминируемых состояний, что в ряде случаев позволяет радикально уменьшить время работы алгоритма. <...> Заметно сократить перебор при решении задачи (1) методом ветвей и границ обычно позволяют также условия отсева [4]. <...> Традиционное правило отсева для задачи о ранце, основанное на линейной релаксации, не работает для задачи <...>