49J55 Problems involving randomness [See also 93E20]
Refine
Year of publication
- 2008 (1)
Document Type
- diplomthesis (1)
Language
- German (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Keywords
- Assignment Problem (1)
- Erwartungswert (1)
- Kombinatorische Optimierung (1)
- Parisi conjecture (1)
- Varianz (1)
- Wahrscheinlichkeit (1)
- assignment problem (1)
- combinatorial optimization (1)
- höhere Momente (1)
- probability (1)
Institute
- Mathematik (1)
Das Assignment Problem ist ein bekanntes kombinatorisches Optimierungsproblem, bei dem es darum geht, in einem gewichteten bipartiten Graphen ein Matching mit minimalem Gewicht zu finden. In dieser Arbeit sind die Kantengewichte exponentialverteilt zu speziell gewählten Raten. Damit sind Erwartungswert und Varianz des minimalen Gewichts von besonderem Interesse. Zunächst wird ein Beweis der Parisi Formel und der Coppersmith-Sorkin Formel erläutert. Die Formeln beschreiben den Erwartungswert des minimalen Gewichts im Fall, dass die Raten alle dem Wert 1 entsprechen. Im zweiten Teil wird die Herleitung einer expliziten Formel zur Berechnung der Varianz des zufälligen minimalen Gewichts erklärt, wobei die Raten immer noch mit 1 übereinstimmen. Gleichzeitig wird eine Formel für die höheren Momente geliefert, aus der die Parisi Formel und Coppersmith-Sorkin Formel aus dem ersten Teil folgen und die sogar das bisherige Modell bezüglich der Parameter erweitert. Schließlich kann man das Ergebnis des zweiten Teils zur Beschreibung des asymptotischen Verhaltens der Varianz benutzen.