Ich würde mich sehr für Verweise auf die Theorie der submodularen Funktionen (von den Grundlagen bis zu den Fortgeschrittenen) interessieren.
Insbesondere studiere ich Annäherungen an schwierige Optimierungsprobleme und möchte meine Grundlagen in submodularen Funktionen entwickeln, da diese für die von mir untersuchten Optimierungsprobleme relevant sind.
Danke im Voraus.
Antworten:
Referenzen wie die von Standa Zivny vorgeschlagenen sind natürlich sehr gut. Lassen Sie mich der Liste das neue Buch von Andras Frank mit dem Titel "Connections in Combinatorial Optimization" hinzufügen, das von Oxford University Press, 2011, veröffentlicht wurde. Alle diese Referenzen behandeln submodulare Funktionen unter dem Gesichtspunkt der klassischen kombinatorischen Optimierung, bei dem Submodularität hauptsächlich in Einschränkungen auftritt. In jüngster Zeit gab es mehrere Anwendungen und Entwicklungen mit submodularen Zielfunktionen, für die ein etwas anderer Standpunkt erforderlich ist. Es gibt viele Papiere, um hier eine Liste zu geben. Ich würde jedoch Shaddin Dughmis Umfrage zu kontinuierlichen Erweiterungen submodularer Funktionen empfehlen http://arxiv.org/abs/0912.0322v3 .
quelle
Die Referenzen, die ich verwende (und mag), sind ausgewählte Kapitel in Schrijvers 3-bändiger kombinatorischer Optimierung: Polyeder und Effizienz (Springer) und Vygens kombinatorische Optimierung (Springer). Es gibt ein Buch über submodulare Funktionen von Fujishige: Submodular Functions and Optimization, Band 58 von Annals of Discrete Mathematics, Nordholland (2. Auflage von 2005).
quelle
Ich möchte " Submodulare Funktionen und elektrische Netze " von H. Narayanan hinzufügen .
quelle
Einer meiner Favoriten, Jan vondraks These und viele seiner Arbeiten.
quelle
Zwei weitere Veröffentlichungen 1. Goldengorin, B., Ghosh, D.: Ein mehrstufiger Suchalgorithmus zur Maximierung submodularer Funktionen, die auf das Problem der quadratischen Kostenverteilung angewendet werden. J. Glob. Optim. 32, 65–82 (2005)
quelle