Том 10, серия 1, номер 2, 2003 г., Стр. 56-65
УДК 519.8
Э. Х. Гимади, Н. М. Коркишко
Об одном алгоритме решения трехиндексной аксиальной задачи о назначениях на одноциклических подстановках
Аннотация:
Рассматривается трехиндексная аксиальная задача о назначениях на одноциклических подстановках. Приводится условие разрешимости задачи. Представлен алгоритм приближенного решения задачи с временной сложностью$O(n^2)$ . Проведен анализ работы алгоритма, доказана корректность его работы. Указываются условия асимптотической точности алгоритма для решения задачи на случайных входах.
Ил. 2, библиогр. 10.
Гимади Э. X. 1
Коркишко Н. М. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru
Статья поступила 3 февраля 2003 г.
Исправленный вариант — 31 марта 2003 г.
