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

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

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


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




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

Уфимский математический журнал, 2011, том 3, выпуск 4, страницы 57–63 (Mi ufa118)  
Комбинаторная сложность одного класса задачи линейного раскроя

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

a Уфимский государственный авиационный технический университет, г. Уфа, Россия
b Башкирский государственный университет, г. Уфа, Россия
PDF полного текста (464 kB)
Список литературы:
PDF
HTML
Аннотация: В статье рассмотрена классическая задача одномерной упаковки (1dCSP), которая является NP-трудной. Приведен один из возможных комбинаторных алгоритмов ее решения, основанный на методе ветвей и границ. Оценена сложность представленного алгоритма для одного класса задач, который назван плотным. Выявлены примеры, наиболее трудные для решения комбинаторными алгоритмами. Этот результат согласуется с экспериментальными данными и может быть использован для генерации трудных тестовых задач, а также для прогнозирования времени работы алгоритма.
Ключевые слова: линейный раскрой, метод ветвей и границ, целочисленное программирование, сложность алгоритма.
Поступила в редакцию: 25.06.2011
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.1+519.8
Образец цитирования: В. М. Картак, В. В. Картак, “Комбинаторная сложность одного класса задачи линейного раскроя”, Уфимск. матем. журн., 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}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ufa118
  • https://www.mathnet.ru/rus/ufa/v3/i4/p57
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Уфимский математический журнал
    Статистика просмотров:
    Страница аннотации:450
    PDF полного текста:144
    Список литературы:47
    Первая страница:2
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024