|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
The upper bound on the complexity of branch-and-bound with cardinality bound for subset sum problemстатья
- Авторы: Thant Sin Si Thu, Mikhail Posypkin, Roman Kolpakov
- Сборник: The American Institute of Physics (AIP) Conference Proceedings
- Том: 1776
- Год издания: 2016
- Место издания: AIP Publishing Melville, New York
- DOI: 10.1063/1.4965330
- Аннотация: We obtained an exact upper bound for the complexity of solving subset sum problem with the special kind of branch and bound algorithm. Complexity is defined as the number of steps of the algorithm. The dominance relation and cardinality bound is used to reduce the number of iterations. We constructed an example of the subset sum problem that has the complexity equal to the upper bound thereby proving the tightness of the proposed upper bound. The obtained estimate is asymptotically two times less than the complexity estimate for the standard branch-and-bound method.
- Добавил в систему: Колпаков Роман Максимович