Оптимальный алгоритм максимизации субмодулярных функций

Рассматривается задача поиска максимума субмодулярной функции на конечном булевом кубе. Построен алгоритм поиска максимума, оптимальный по Шеннону, и дана оценка его сложности. Результат распространяется на случай поиска максимума на выпуклом подмножестве булева куба. Устанавливается связь с задачей о расшифровке монотонной булевой функции.