Том 9, серия 1, номер 4 , 2002 г., Стр. 75-81
УДК 519.8
В. В. Шенмайер
Анализ алгоритмов покоординатного подъема для полиматроидов
Аннотация:
Изучается задача целочисленного программирования на полиматроидах, которая является обобщением задачи о базе матроида максимального веса и подобно последней решается алгоритмом покоординатного подъема. Рассматривается класс всех алгоритмов покоординатного подъема, и в данном классе характеризуется подкласс алгоритмов, позволяющих получать точное решение. В качестве следствия получено обобщение теоремы Радо–Эдмондса для произвольных семейств векторов, опирающееся на понятие коцикла.
Библиогр. 4.
Шенмайер В. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru
Статья поступила 26 августа 2002 г.
