RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

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

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



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






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


Дискрет. матем., 2010, том 22, выпуск 1, страницы 58–73 (Mi dm1084)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце

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


Аннотация: Статья посвящена вопросам сложности решения задачи об одномерном булевом ранце методом ветвей и границ. Для рассматриваемой сложности получены две верхние оценки. Выделен частный случай задачи о ранце, когда сложность ее решения полиномиально ограничена размерностью задачи. Получены также верхняя и нижняя оценки сложности решения методом ветвей и границ задачи о сумме подмножеств, являющейся частным случаем задачи о ранце.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05-01-00495a, 06-07-89079a.

DOI: https://doi.org/10.4213/dm1084

Полный текст: PDF файл (165 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2010, 20:1, 95–112

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.7
Статья поступила: 01.04.2009

Образец цитирования: Р. М. Колпаков, М. А. Посыпкин, “Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце”, Дискрет. матем., 22:1 (2010), 58–73; Discrete Math. Appl., 20:1 (2010), 95–112

Цитирование в формате AMSBIB
\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://www.ams.org/mathscinet-getitem?mr=2675431}
\zmath{https://zbmath.org/?q=an:05779535}
\elib{http://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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1084
  • https://doi.org/10.4213/dm1084
  • http://mi.mathnet.ru/rus/dm/v22/i1/p58

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. 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  crossref  isi  scopus
    2. Р. М. Колпаков, М. А. Посыпкин, “О наилучшем выборе переменной ветвления в задаче о сумме подмножеств”, Дискрет. матем., 29:1 (2017), 51–58  mathnet  crossref  elib; 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  crossref  isi
    3. А. Ю. Попков, Б. С. Дарховский, Ю. С. Попков, “Итерационный МК-алгоритм решения задач глобальной оптимизации”, Автомат. и телемех., 2017, № 2, 82–98  mathnet  elib; 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  crossref  isi
    4. Р. М. Колпаков, М. А. Посыпкин, Си Ту Тант Син, “Сложность решения задачи о сумме подмножеств методом ветвей и границ с доминированием и мощностным отсевом”, Автомат. и телемех., 2017, № 3, 96–110  mathnet  elib; 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  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:956
    Полный текст:207
    Литература:50
    Первая стр.:41

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019