RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2002, том 9, выпуск 4, страницы 75–81 (Mi da187)

Анализ алгоритмов покоординатного подъема для полиматроидов

В. В. Шенмайер

Институт математики им. С. Л. Соболева СО РАН

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

УДК: 519.8

Статья поступила: 26.08.2002



Реферативные базы данных:


© МИАН, 2024