Подмодульные функции: запрос ссылки

11

Я был бы очень заинтересован ссылками на теорию субмодулярных функций (от основ до продвинутых).

В частности, я изучаю приближения к сложным задачам оптимизации и хочу развить свои основы субмодулярных функций, поскольку они имеют отношение к задачам оптимизации, которые я изучал.

Заранее спасибо.

Нихилу
источник

Ответы:

8

Ссылки, подобные предложенным Standa Zivny, конечно, очень хороши. Позвольте мне добавить в список новую книгу Андраса Фрэнка под названием «Связи в комбинаторной оптимизации», опубликованную издательством Oxford University Press, 2011. Все эти ссылки относятся к субмодулярным функциям с точки зрения классической комбинаторной оптимизации, где субмодулярность в основном проявляется в ограничениях. Было несколько недавних приложений и разработок с субмодулярными целевыми функциями, для которых требуется немного другая точка зрения. Есть много бумаг, чтобы дать список здесь. Тем не менее, я бы порекомендовал обзор Шаддина Дугми о непрерывном расширении субмодульных функций http://arxiv.org/abs/0912.0322v3 .

Чандра Чекури
источник
Спасибо за опрос, выглядит очень хорошо! Я недавно купил книгу Фрэнка, но пока не успел ее прочитать, поэтому я неохотно рекомендовал ее.
Standa Zivny
5
@Chandra, время для тебя, чтобы написать обзор о самых последних материалах :)
Suresh Venkat
Спасибо за ссылку опроса. Я искал что-то похожее на это.
Нихил
9

Ссылки, которые я использую (и т.п.), - это отдельные главы в 3-томной комбинаторной оптимизации Шрайвера: многогранники и эффективность (Springer) и комбинаторная оптимизация Vygen (Springer). Существует книга, посвященная субмодулярным функциям Фуджишиге: субмодулярные функции и оптимизация, том 58, Анналы дискретной математики, Северная Голландия (2-е издание от 2005 г.).

Standa Zivny
источник
0

Еще две публикации 1. Гольденгорин Б., Гош Д. Д .: Многоуровневый алгоритм поиска для максимизации субмодулярных функций, применяемый к задаче квадратичного разделения затрат. J. Glob. Optim. 32, 65–82 (2005)

  1. Б. Гольденгорин. Максимизация субмодулярных функций: теория и алгоритмы перечисления. Европейский журнал исследований операций, 198 (1): 102–112, 2009
user56394
источник