Аннотация:
Изучается задача целочисленного программирования
на полиматроидах, которая
является обобщением задачи о базе матроида максимального
веса и подобно последней решается алгоритмом покоординатного подъема.
Рассматривается класс всех алгоритмов покоординатного подъема, и в данном классе характеризуется подкласс алгоритмов,
позволяющих получать точное решение.
В качестве следствия получено обобщение теоремы Радо–Эдмондса для
произвольных семейств векторов, опирающееся на понятие коцикла.
Библиогр. 4.
Полный текст:
PDF файл (372 kB)