Том 16, номер 5, 2009 г., Стр. 3-18
УДК 519.8
А. А. Агеев, Э. Х. Гимади, А. А. Курочкин
Полиномиальный алгоритм решения задачи размещения на цепи с одинаковыми производственными мощностями предприятий
Аннотация:
Рассматривается задача размещения на путевом графе в случае одинаковых производственных мощностей предприятий. Ранее построен точный алгоритм, решающий задачу за время$O(m^5n^2+m^3n^3)$ , где$m$ и$n$ – число предприятий и пунктов спроса соответственно. Предлагается модификация этого алгоритма с меньшей на порядок по обоим параметрам временно́й сложностью$O(m^4n^2)$ .
Ил. 9, библиогр. 24.
Ключевые слова: задача размещения, одинаковые производственные мощности, путевой граф, точный алгоритм, полиномиальная трудоёмкость.
Агеев Александр Александрович 1
Гимади Эдуард Хайрутдинович 1
Курочкин Александр Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ageev@math.nsc.ru, gimadi@math.nsc.ru, alkurochkin@ngs.ru
Статья поступила 25 июня 2009 г.
