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

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

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



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






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


Уфимск. матем. журн., 2011, том 3, выпуск 4, страницы 57–63 (Mi ufa118)  

Комбинаторная сложность одного класса задачи линейного раскроя

В. М. Картакa, В. В. Картакb

a Уфимский государственный авиационный технический университет, г. Уфа, Россия
b Башкирский государственный университет, г. Уфа, Россия

Аннотация: В статье рассмотрена классическая задача одномерной упаковки (1dCSP), которая является NP-трудной. Приведен один из возможных комбинаторных алгоритмов ее решения, основанный на методе ветвей и границ. Оценена сложность представленного алгоритма для одного класса задач, который назван плотным. Выявлены примеры, наиболее трудные для решения комбинаторными алгоритмами. Этот результат согласуется с экспериментальными данными и может быть использован для генерации трудных тестовых задач, а также для прогнозирования времени работы алгоритма.

Ключевые слова: линейный раскрой, метод ветвей и границ, целочисленное программирование, сложность алгоритма.

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

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.1+519.8
Поступила в редакцию: 25.06.2011

Образец цитирования: В. М. Картак, В. В. Картак, “Комбинаторная сложность одного класса задачи линейного раскроя”, Уфимск. матем. журн., 3:4 (2011), 57–63

Цитирование в формате AMSBIB
\RBibitem{KarKar11}
\by В.~М.~Картак, В.~В.~Картак
\paper Комбинаторная сложность одного класса задачи линейного раскроя
\jour Уфимск. матем. журн.
\yr 2011
\vol 3
\issue 4
\pages 57--63
\mathnet{http://mi.mathnet.ru/ufa118}
\zmath{https://zbmath.org/?q=an:1249.05049}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ufa118
  • http://mi.mathnet.ru/rus/ufa/v3/i4/p57

    ОТПРАВИТЬ: 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
  • Уфимский математический журнал
    Просмотров:
    Эта страница:325
    Полный текст:86
    Литература:22
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019