|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Upper and lower bounds for the complexity of the branch and bound method for the knapsack problemстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 3 ноября 2016 г.
- Авторы: Kolpakov R.M., Posypkin M.A.
- Журнал: Discrete Mathematics and Applications
- Том: 20
- Номер: 1
- Год издания: 2010
- Издательство: de Gruyter
- Местоположение издательства: Germany
- Первая страница: 113
- Последняя страница: 125
- DOI: 10.1515/DMA.2010.007
- Аннотация: This paper is devoted to questions concerning the complexity of solution of the problem on one-dimensional Boolean knapsack by the branch and bound method. For this complexity we obtain two upper bounds. We separate the special case of the knapsack problem where the complexity is polynomially bounded by the dimension of the problem. We also obtain an upper and lower bounds for the complexity of solution by the branch and bound method of the subset sum problem which is a special case of the knapsack problem.
- Добавил в систему: Колпаков Роман Максимович