Submodulare Funktionen: Referenzanforderung

11

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.

Nikhil
quelle

Antworten:

8

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 .

Chandra Chekuri
quelle
Vielen Dank für die Umfrage, es sieht sehr gut aus! Ich habe kürzlich Franks Buch gekauft, habe es aber noch nicht gelesen, also war ich etwas zurückhaltend, es zu empfehlen.
Standa Zivny
5
@Chandra, Zeit für Sie, eine Umfrage über die neuesten Sachen zu schreiben :)
Suresh Venkat
Danke für den Umfragelink. Ich suchte nach etwas Ähnlichem.
Nikhil
9

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).

Standa Zivny
quelle
2

Einer meiner Favoriten, Jan vondraks These und viele seiner Arbeiten.

Ashwinkumar BV
quelle
0

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)

  1. B. Goldengorin. Maximierung submodularer Funktionen: Theorie- und Aufzählungsalgorithmen. European Journal of Operational Research, 198 (1): 102–112, 2009
user56394
quelle