Full metadata record
DC FieldValueLanguage
dc.contributor.advisorWegener, Ingode
dc.contributor.authorWitt, Carstende
dc.date.accessioned2004-12-29T11:01:46Z-
dc.date.available2004-12-29T11:01:46Z-
dc.date.created2004-12-06de
dc.date.issued2004-12-14de
dc.identifier.urihttp://hdl.handle.net/2003/19662-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-255-
dc.description.abstractDer Entwurf und die Analyse von Algorithmen für die kombinatorische Optimierung zählen zu den zentralen Aufgaben der Informatik. In dieser Dissertation werden in der Praxis erfolgreiche Suchheuristiken, speziell evolutionäre Algorithmen, theoretisch untersucht. Außerdem enthält die Dissertation einen Beitrag zum Entwurf von Algorithmen für ein aktuelles kombinatorisches Optimierungsproblem. Der erste Teil der Dissertation widmet sich einfachen randomisierten Suchheuristi­ken, die zu jedem Zeitpunkt lediglich einen Suchpunkt vorhalten. Diese werden auf der Funktionenklasse der so genannten monotonen Polynome und einem NP­harten Partitionsproblem untersucht. Neben der Analyse der erwarteten Optimierungszeit wird auch die Approximationsgüte studiert, die die Suchheuristiken in Polynomialzeit mit guter Wahrscheinlichkeit erreichen. Im zweiten Teil werden populationsbasierte evolutionäre Algorithmen, die zu jedem Zeitpunkt eine Menge von Suchpunkten vorhalten, betrachtet. Es wird bewiesen, dass die Größe einer solchen Population die Optimierungszeit von evolutionären Algorithmen entscheidend beeinflussen kann. Darüber hinaus wird ein klassischer populationsbasierter evolutionärer Algorithmus auf drei Beispielfunktionen untersucht. Dabei wird der funktionale Zusammenhang zwischen Populationsgröße und erwarteter Optimierungszeit erhellt. Die ersten beiden Teile der Dissertation enthalten fundamental neue Methoden zur Analyse randomisierter Suchheuristiken. Der dritte Teil der Dissertation stellt schließlich problemspezifische Algorithmen für das kombinatorische Optimierungsproblem des integrierten Prefetchings und Cachings vor. Es gelingt der Entwurf eines ersten kombinatorischen Polynomialzeitalgorithmus für einen Spezialfall des Optimierungsproblems. Für den allgemeinen Fall werden verbesserte Approximationsalgorithmen präsentiert.de
dc.format.extent1602482 bytes-
dc.format.extent2513660 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/postscript-
dc.language.isodede
dc.publisherUniversität Dortmundde
dc.subjectTheoretische Analysede
dc.subjectRandomisierte Suchheuristikende
dc.subjectEvolutionäre Algorithmende
dc.subjectKombinatorische Optimierungde
dc.subject.ddc004de
dc.titleÜber die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierungde
dc.typeTextde
dc.contributor.refereeVöcking, Bertholdde
dc.date.accepted2004-
dc.type.publicationtypedoctoralThesisde
dcterms.accessRightsopen access-
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
WITT.PDFDNB1.5 MBAdobe PDFView/Open
WITT.PS2.45 MBPostscriptView/Open
ZUSAMMENFASSUNGWitt.PDFZusammenfassung31.13 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.