Том 7, серия 1, номер 4, 2000 г., Стр. 38-47

УДК 519.8
Н. И. Глебов, В. В. Шенмайер
О применимости алгоритма покоординатного подъёма к задачам целочисленного программирования

Аннотация:
Для задачи максимизации вогнутой сепарабельной функции на подмножестве, состоящем из всех максимальных относительно частичного порядка точек некоторого конечного множества в $R^n$, обоснован критерий ее разрешимости посредством «жадного» алгоритма. Доказано также одно достаточное условие применимости данного алгоритма и указан класс задач целочисленного программирования, удовлетворяющих полученному критерию разрешимости.
Библиогр. 5.

Глебов Н. И. ¹
Шенмайер В. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 10 августа 2000 г.