Я был бы очень заинтересован ссылками на теорию субмодулярных функций (от основ до продвинутых).
В частности, я изучаю приближения к сложным задачам оптимизации и хочу развить свои основы субмодулярных функций, поскольку они имеют отношение к задачам оптимизации, которые я изучал.
Заранее спасибо.
Ответы:
Ссылки, подобные предложенным Standa Zivny, конечно, очень хороши. Позвольте мне добавить в список новую книгу Андраса Фрэнка под названием «Связи в комбинаторной оптимизации», опубликованную издательством Oxford University Press, 2011. Все эти ссылки относятся к субмодулярным функциям с точки зрения классической комбинаторной оптимизации, где субмодулярность в основном проявляется в ограничениях. Было несколько недавних приложений и разработок с субмодулярными целевыми функциями, для которых требуется немного другая точка зрения. Есть много бумаг, чтобы дать список здесь. Тем не менее, я бы порекомендовал обзор Шаддина Дугми о непрерывном расширении субмодульных функций http://arxiv.org/abs/0912.0322v3 .
источник
Ссылки, которые я использую (и т.п.), - это отдельные главы в 3-томной комбинаторной оптимизации Шрайвера: многогранники и эффективность (Springer) и комбинаторная оптимизация Vygen (Springer). Существует книга, посвященная субмодулярным функциям Фуджишиге: субмодулярные функции и оптимизация, том 58, Анналы дискретной математики, Северная Голландия (2-е издание от 2005 г.).
источник
Я хотел бы добавить « Подмодульные функции и электрические сети » Х. Нараянана .
источник
Один из моих любимых, тезис Яна Вондрака и многие его работы.
источник
Еще две публикации 1. Гольденгорин Б., Гош Д. Д .: Многоуровневый алгоритм поиска для максимизации субмодулярных функций, применяемый к задаче квадратичного разделения затрат. J. Glob. Optim. 32, 65–82 (2005)
источник