Том 11, серия 1, номер 4, 2004 г., Стр. 36-43
УДК 519.854
Н. И. Глебов
Об одном обобщении минимаксной задачи о назначениях
Аннотация:
Для некоторого обобщения минимаксной задачи о назначениях, представляющего собой транспортную задачу с минимаксным критерием и ограниченными целочисленными переменными, предложен алгоритм, который в общем случае является псевдополиномиальным. В случае несбалансированной минимаксной задачи о назначениях алгоритм полиномиален, а при определенном соотношении параметров задачи его оценка трудоемкости линейным образом зависит от размерности задачи.
Глебов Н. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 15 июня 2004 г.
