Funkcje submodularne: żądanie referencyjne

Byłbym bardzo zainteresowany odniesieniami do teorii funkcji podmodularnych (od podstaw po zaawansowane).

W szczególności studiuję aproksymacje do problemów z twardą optymalizacją i chcę rozwinąć swoje podstawy w funkcjach podmodularnych, ponieważ są one istotne dla problemów optymalizacji, które badałem.

Z góry dziękuję.

Referencje takie jak te sugerowane przez Standę Zivny są oczywiście bardzo dobre. Dodam do listy nową książkę Andrasa Franka pt. „Connections in Combinatorial Optimization” opublikowaną przez Oxford University Press, 2011. Wszystkie te odniesienia traktują funkcje submodularne z klasycznego punktu widzenia optymalizacji kombinatorycznej, gdzie submodularność pojawia się przede wszystkim w ograniczeniach. Ostatnio pojawiło się kilka aplikacji i rozwiązań z podmodularnymi funkcjami celu, dla których należy nieco inaczej spojrzeć. Istnieje wiele dokumentów, które można podać tutaj. Poleciłbym jednak ankietę Shaddina Dughmiego dotyczącą ciągłych rozszerzeń funkcji submodularnych http://arxiv.org/abs/0912.0322v3 .

Odnośniki, których używam (i tym podobne) to wybrane rozdziały w 3-tomowej optymalizacji kombinatorycznej Schrijvera: Wielościany i wydajność (Springer) oraz Optymalizacja kombinatoryczna Vygen'a (Springer). Istnieje książka poświęcona funkcjom podmodularnym autorstwa Fujishige: Submodular Functions and Optimization, tom 58 Annals of Discrete Mathematics, North-Holland (2. wydanie z 2005 r.).

Chciałbym dodać „ Funkcje submodularne i sieci elektryczne ” H. Narayanana .

Jedna z moich ulubionych, praca Jana Vondraka i wiele jego prac.

Dwie kolejne publikacje 1. Goldengorin, B., Ghosh, D .: Algorytm wielopoziomowego wyszukiwania do maksymalizacji funkcji submodularnych zastosowany do problemu kwadratycznego podziału kosztów. J. Glob. Optim. 32, 65–82 (2005)

2. B. Goldengorin. Maksymalizacja funkcji podmodularnych: Teorie i algorytmy wyliczania. European Journal of Operational Research, 198 (1): 102–112, 2009