Das Mengenüberdeckungsproblem: Theorie und Algorithmen

Das Mengenuberdeckungsproblem: Theorie und Algorithmen ¨
Das Mengenuberdeckungsproblem lautet wie folgt: Gegeben sei eine Familie ¨ F von Teilmengen einer
endlichen Menge X mit ∪F ∈F F = X. Finde eine Teilfamilie F
0 von F minimaler M¨achtigkeit, sodass
∪F ∈F0F = X gilt.
In der Bachelorarbeit sollen einfache approximative und exakte Algorithmen fur dieses Problem mit ¨
entsprechenden Beweisen verst¨andlich dargestellt werden. Fur spezielle F ¨ ¨alle, in denen X aus Gitterpunkten
der Ebene besteht und die Mengen F mit Hilfe von Abst¨anden definiert werden, sollen
m¨oglichst genaue L¨osungen angegeben werden.
Literatur
[1] B. Korte und J. Vygen: Combinatorial Optimization. Springer 2008.
[2] V. Chv´atal: A greedy heuristic for the set cover problem. Mathematics of Operations Research 4
(1979), 233-235.

Weitere Informationen

Unternehmen

Thesius Inspiration

Abschlussart

Bachelorarbeit / Masterarbeit / Diplomarbeit / Dissertation

Ansprechpartner/in

Name: Herr Thesius Kontakt
E-Mail: support1@thesius.de
Tel.: keine Nummer angegeben

Branche

Forschung und Entwicklung

Zusatzinformationen

http://www.mathematik.uni-rostock.de/fileadmin/MathNat_Mathe/Studium/Aktuelles/Bachelor-Themen/SS2015/Engel1.pdf