The k-Center Problem for some cities of Germany The k-Center Problem title Technische Universität München

Willkommen beim $k$-Center Spiel!

Auf dieser Seite starten wir mit einer kurzen Einführung, um dich mit dem $k$-Center Problem vertraut zu machen.

Nehmen wir einmal an du betreibst einen gastronomischen Betrieb. In Deutschland hast du noch keine Filialen eröffnet. Da der Markt vielversprechend ist, möchtest du die größten 20 deutschen Städte mit deinen Filialen abdecken. Aus finanziellen Gründen kannst du jedoch lediglich 5 neue Filialen eröffnen. Du fragst dich, an welchen Standorten du die Filialen eröffnen solltest, sodass die maximale Distanz (Luftlinie) zu den größten deutschen Städte, möglichst klein ist. Du betrachtest gerade ein 5-Center Problem im euklidischen zweidimensionalen Raum!

Das $k$-Center Problem besteht darin, $k$ Zentren $C = \{c_1, \ldots, c_k\}$ zu finden, sodass der maximale Abstand von einem Punkt zum nächstgelegenen Zentrum möglichst klein ist. Wir möchten also den Worstcase optimieren. Es spielt keine Rolle ob viele Städte sehr nahe an einem Zentrum liegen. Solange eine Stadt sehr weit weg vom nächstgelegenen Zentrum liegt, handelt es sich um eine schlechte Lösung. Die Distanz zwischen zwei Punkten ist durch eine Metrik festgelegt.

Eine formalere Definition

Sei $P \subset \mathbb{R}^n$ Punktmenge, $k > 0$ eine natürliche Zahl und $m$ die verwendete Metrik, so lautet das zugehörige $k$-Center Problem:

$$\min_{C = \{c_1, \ldots, c_k\} \subset \mathbb{R}^n} \rho$$
so dass $\forall p \in P \ \exists c \in C : \left|\left|p - c\right|\right|_m \leq \rho$

Für jeden Punkt $p$ gibt es also ein Zentrum $c_j$, welches von $p$ maximal $\rho$ entfernt ist. Angenommen wir hätten eine Lösung, also $k$ Zentren, so gilt für den Wert der Zielfunktion $\rho$:

$$\rho = \max_{p \in P} \min_{c \in C}\left|\left|p - c\right|\right|_m$$

Komplexität des Problems

Das $k$-Center Problem ist bereits für $k \geq 2$ und unter Verwendung der euklidischen Metrik $\mathcal{NP}$-vollständig, was bedeutet, dass kein effizienter Algorithmus bekannt ist, der das Problem löst. Für wenige Punkte kann eine exakte Lösung noch berechnet werden. Die kombinatorische Explosion der Möglichkeiten, für größere Probleminstanzen, führt allerdings schnell zu einer nicht annehmbar langen Laufzeit. Darum ist es nötig auf eine angenäherte Lösung zurückzugreifen. Falls $\mathcal{NP}$ ungleich $\mathcal{P}$ gilt, wovon die meisten Komplexitätstheoretiker ausgehen, gibt es auch in Zukunft keinen effizienten Algorithmus der eine optimale Lösung des $k$-Center Problems berechnet.

Was möchtest du zuerst tun?

k-Center Problem for some cities of Germany

Neues Spiel







Spiel wiederholen

Fehler

    Hier kannst du ein Spiel erstellen!

    Wähle dazu eine Karte und die Anzahl der Städte, die zufällig aus eine vorgegebnen Menge ausgewält werden. Wähle eine Metrik welche angibt wie Distanzen zwischen zwei Städten bzw. zwischen Stadt und Zentrum, berechnet werden sollen:
    Euklidsche Metrik Euklidsche Metrik
    $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
    Manhatten-Metrik Manhatten-Metrik
    $\left| x_1 - x_2 \right| + \left| y_1 - y_2 \right|$
    Maximum-Metrik Maximum-Metrik
    $\max\{\left| x_1 - x_2 \right|,\left| y_1 - y_2 \right|\}$
    Ihr Browser unterst¨tzt kein HTML5 Canvas. Bitte verwenden Sie einen modernen Browser, z.B.Mozilla Firefox

    Radius deiner Lösung

    Setze deine Zentren!

    Zeichne deine $k$-Center-Überdeckung!
    Versuche den Radius zu minimieren, es müssen allerdings alle Städte überdeckt werden.
    Per Drag & Drop können Zentren platziert und verschoben werden. Zentren können gelöscht werden, wenn sie ausgewählt sind. Um den Radius zu ändern ziehe den äußeren Rand in die jeweilige Richtung.
    Center

    Lasse dir die Lösung anzeigen!

    Sobald du alle Städte überdeckt hast, kannst du dir hier eine, von der gewälten Güte abhäigen Lösung anzeigen lassen. Möchtest du die Lösung sofort sehen, drücke in der Tableiste auf "Angenäte Lösung".
    Du überdeckst nicht alle Städte!

    Spiele dieses Spiel erneut!

    Um das aktuelle Spiel zu einem späteren Zeitpunkt erneut zu spielen, kannst du dir hier den Spielcode anzeigen lassen und diesen beim Erstellen des Spiels unter "Spiel wiederholen" eingeben.
    Spielcode einblenden

    Teste deine logistischen Fähigkeiten und setze die Zentren möglichst so, dass die Überdeckung einen kleinen Radius benötigt.

    Vergiss dabei nicht, jede Stadt zu überdecken.

    Mit dem Wechsel des Tabs wird das Setzen der Zentren beendet.

    Es ist danach nicht mehr möglich, in den Spieltab zurückzukehren.

    Ihr Browser unterstützt kein HTML5 Canvas. Bitte verwenden Sie einen modernen Browser, z.B.Mozilla Firefox

    Radius der angenäherten Lösung:

    Radius deiner Lösung:

    Berechnungszeit:

    Glückwunsch! Deine Überdeckung ist besser wie die angenäherte Lösung.

    Schade! Deine Überdeckung ist leider schlechter als die angenäherte Lösung.

    Wie wurde die Lösung berechnet?

    Mit Klick auf den Button erhältst du nähere Informationen zur Funktionsweise der verwendeten Algorithmen, die zur Findung der Lösung beigetragen haben.
    Du kannst dir aber auch direkt die Berechnungsschritte anzeigen lassen, die zu dieser Überdeckung geführt haben.
    Spielcode einblenden

    Glückwunsch! Deine Lösung ist besser als die angenäherte.

    Schade! Deine Lösung ist leider nicht schlechter als die angenäherte.

    Angenäherte Lösung:
    Deine Lösung:

    Jetzt kannst du dir die angenäherte Lösung und die dazugehörigen Berechnungsschritte ansehen.

    In der Beschreibung des Algorithmus findest du genauere Informationen zu den verwendeten Algorithmen der einzelnen Schritte.

    Überblick

    Reduktion des $k$-Center Problems auf $k$ 1-Center Probleme

    Angenommen wir könnten das Problem für $k=1$ lösen. Es handelt sich dann um ein sogenanntes 1-Center Problem. Nehmen wir einmal an wir hätten das $k$-Center Problem gelöst und hätten somit Zentren $c_1, \ldots, c_k$. Berechnen wir nun die Mengen $P_1, \ldots, P_k$, sodass in $P_i$ die Punkte enthalten sind, welche zu $c_i$ den kleinsten Abstand haben. Lösen wir nun die $k$ 1-Center Probleme so erhalten wir die gleichen Zentren $c_1, \ldots, c_k$. Die Aufgabe des Lösungsalgorithmus für das $k$-Center Problem besteht in der Suche nach guten Mengen $P_1, \ldots, P_k$.

    Zusammenspiel

    Anstatt das $k$-Center Problem direkt zu lösen, lösen wir, in einer klugen/gierigen Reihenfolge mittels einer Branch&Bound-Methode, solange verschiedene $k$ 1-Center Probleme, bis wir eine Lösung erhalten, welche nahe genug am Optimum liegt. Das 1-Center Problem lösen wir mit dem Schnittebenenverfahren. Die Lösung des Dilatationsproblems gibt uns eine obere Schranke und die Lösung der $k$ 1-Center Probleme eine lokale untere Schranke. Diese Schranken (Bounds) werden verwendet um die Verzweigungen (Branches) des Berechnungsbaumes abzubrechen. Jeder Knoten des Berechnungsbaumes entspricht dabei $k$ 1-Center Instanzen $(P_1, \ldots, P_k)$, also einer Annäherung der optimalen Lösung. Dabei gilt stets $$\bigcup_{i=1}^k P_i \subset P.$$ Die $k$ Kindknoten sind Kopien ihres Elternknotens, wobei ein neuer Punkt $p^* \notin \bigcup_{i=1}^k P_i$ für Kind $j$ in die Punktmenge $P_j$ aufgenommen wird.

    Das Dilatationsproblem

    Die Problemstellung

    Das Dilatationsproblem ist ein einfaches Optimierungsproblem. Seien Zentren $C = \{c_1, \ldots, c_k\} \subset \mathbb{R}^n$ und Städte (Punkte) $P = \{p_1, \ldots, p_m\}$ gegeben, so suchen wir nach dem Punkt $p^*$, welcher die maximale Distanz, unter der Metrik $m$, zum nächstliegenden Zentrum hat:

    $$p^* = \arg \max_{p \in P} \min_{c \in C} \left|\left|p - c \right|\right|_m$$ $$\rho = \max_{p \in P} \min_{c \in C} \left|\left| p - c \right|\right|_m = \min_{c \in C} \left|\left| p^* - c \right|\right|_m$$
    • Eingabe: Zentren $c_1, \ldots, c_k$, Punkte $P \subset \mathbb{R}^n$
    • Ausgabe: minimale Dilatation $\rho$, einer der Punkte $p^*,$ der die Dilatation verursacht

    Abbildung 1: Lösung des Dilatationsproblems unter euklidischer Metrik: $\rho = \left|\left| p^* - c_2 \right|\right|_2$.

    Verschieben wir die Zentren und lösen das Dilatationsproblem erneut, so können wir entscheiden welche Positionierung die bessere war. Die Lösung des Dilatationsproblems ist somit eine obere Schranke für die Lösung des $k$-Center Problems.

    Der Algorithmus

    Der Algorithmus für dieses Problem ist denkbar einfach. Die Distanzfunktion wird für jeden Punkt für jedes Zentrum ausgewertet und das minimale Maximum zurückgegeben. Die Komplexität beträgt $\mathcal{O}(m \cdot k)$.

    Das $k$-Center Problem

    Problemstellung

    Sei $P \subset \mathbb{R}^2$ unsere Menge an Städten und $k \in \mathbb{N}$ eine natürliche Zahl größer 0, so suchen wir nach Zentren $C = \{c_1, \ldots c_k\}$ so dass:

    $$\min_{C = \{c_1, \ldots, c_k\} \subset \mathbb{R}^n} \rho$$
    so dass $\forall p \in P \ \exists c \in C : \left|\left| p-c\right|\right|_{m} \leq \rho$,

    wobei $\left|\left| \cdot \right|\right|_m$ die Distanz unter der Metrik $m$ ist.

    • Eingabe: natürliche Zahl $k > 0$, Punkte $P \subset \mathbb{R}^n$
    • Ausgabe: minimale Dilatation $\rho$, Zentren $c_1, \ldots, c_k$

    Lösungsbeispiel:


    Abbildung 1: Die Lösung einer $k$-Center Probleminstanz unter euklidischer Metrik. Der grüne durchgezogene Kreis gibt den Abstand vor. Für die rechte Punktmenge würde auch der Radius des gestrichelten Kreises ausreichen.

    Der Algorithmus

    Für die Wurzel des Berechnungsbaumes verteile alle Zentren $c_1, \ldots, c_k$ beliebig und $P_1 = \ldots = P_k = \emptyset, r = 0, \bar{R} = R =$ Lösung des Dilatationproblems, rufe $k$-Center(Wurzel).

      $k$-Center(Knoten):
    1. Berechne $R$, also die Lösung des Dilatationsproblems bezüglich ganz $P$ und $c_1, \ldots, c_k$
    2. Berechne $\bar{R} = \min(R, \bar{R})$
    3. Falls $\bar{R} \leq r$ oder Lösung gut genug, breche ab!
    4. Berechne $p^*$, also den Punkt der am weitesten vom nächstliegenden Zentrum entfernt ist.
    5. Sortiere die Zentren aufsteigend nach $\left|\left|p^* - c_i \right|\right|_m$
      1. Für alle Zentren $c_i$ in aufsteigender Reihenfolge
      2. Berechne die Lösungen der 1-Center Instanz also $c^*_i$ mit $P := P_i \cup \{p^*\}$.
      3. Erzeuge Kindknoten$_i$ (von links nach rechts) mit $P_i = P_i \cup \{p^*\}, c_i = c^*_i$ und alle anderen $P_{j\neq i}$ bzw. $c_{j \neq i}$ bleiben unverändert. (siehe Abbildung 2)
      4. rufe $k$-Center(Kindknoten$_i$)

    Berechnungsbeispiel

    Schau dir das folgende Beispiel an. Es ist eine Instanz eines 2-Center Problems mit euklidischer Metrik. Die weiß gekennzeichneten Städte mit schwarzem Rand sind in der aktuellen Verteilung. Es wird jeweils die aktuelle Lösung der zwei 1-Center Probleme inklusive der lokalen Schranken angezeigt:

    t1
    Abbildung 2: (Baumwurzel) Die Zentren befinden sich beide an der gleichen zufälligen Position, $\bar{R} = R < \infty, r = 0$
    t3
    Abbildung 3: (Baumtiefe 1, links) Der Knoten, der am weitesten entfernt ist, wird einem beliebigen Zentrum bzw. $P_i$ zugewiesen, $\bar{R} = R < \infty, r = 0$
    Rechter Knoten wird nicht betrachtet, da die Zuordnung zum linken Knoten nicht unterscheidbar ist.
    t3
    Abbildung 4: (Baumtiefe 2, links) Der Knoten, der am weitesten entfernt ist, wird dem nähersten Zentrum zugewiesen, $\bar{R} = R < \infty, r = 0$
    Rechter Knoten wird nicht betrachtet, da an dieser Stelle $\bar{R} \leq r$.
    t3
    Abbildung 5: (Baumtiefe 3, links) Der Knoten, der am weitesten entfernt ist, wird dem nähersten Zentrum zugewiesen, $\bar{R} = R < \infty, r > 0$
    t3
    Abbildung 6: (Baumtiefe 3, rechts) Der gleiche Knoten wird dem anderen Zentrum zugewiesen, $\bar{R} < R, \bar{R} < \infty, R < \infty, r > 0$
    t3
    Abbildung 7: (Baumtiefe 4, links) Der Knoten, der am weitesten entfernt ist, wird dem nähersten Zentrum zugewiesen, $\bar{R} = R = r < \infty$. Da sichergestellt ist, dass die Lösung eines Kindes zwischen $R$ und $r$ eines Elternkonten liegen muss, müssen wir in diesem Knoten nicht weiter verzweigen.
    Rechter Knoten wird nicht betrachtet, da an dieser Stelle $\bar{R} \leq r$.

    Wir sehen an diesem Beispiel, dass durch die Aufnahme weit entfernter Punkte, viele uninteressante Fälle übersprungen werden. Durch die Aufnahme weit entfernter Punkte wird die lokale untere Schranke schnell größer.

    Den Berechnungsbaum, inklusive der Abarbeitungsreihenfolge, findest du hier:


    Abbildung 8: Der komplette Berechnungsbaum. Die blauen Zahlen stehen für die Suchreihenfolge der Tiefensuche.

    Erklärung

    Der Algorithmus besteht darin, die Zuordnung der Punkte zu ihren Zentren zu finden. Es ist zu beachten, dass oft schon eine Teilmenge von $P$ ausreicht. In Abbildung 1 reicht es aus $P_1 = \{p_1, p_2, p_3\} , P_2 = \{p_4\} $ zu wählen. Es wird eine Baumstruktur aufgebaut. In jedem Knoten befinden sich Mengen $P_1, \ldots, P_k$, welche die Verteilung der Punkte auf die Zentren angeben. Zusätzlich wird eine lokale obere Schranke $R$ und eine unter lokale Schranke $r$ mitgeführt. Die lokale untere Schranke ist das Maximum aller 1-Center Lösungen des Knotens und die lokale obere Schranke die Lösung des Dilatationsproblems bezüglich $P$ und der berechneten Zentren $C$ des Knotens. Es handelt sich um eine lokale untere Schranke, da in allen 1-Center Instanzen aller Kinder des Knotens, die gleichen Punkte oder echt mehr Punkte überdeckt werden müssen. Zusätzlich existiert eine globale obere Schranke $\bar{R}$, welche gleich dem Minimum aller bisher berechneten lokalen oberen Schranken ist.


    Abbildung 9: Situation in einem Knoten eines 2-Center Problems unter euklidischer Metrik. $P_1$ enthält alle blauen $P_2$ alle orangen Punkte. $p^*$ definiert die lokale obere Schranke (gepunktete Kreislinie) und der durchgezogene blaue Kreis die lokale untere Schranke. $p^*$ wird in den Kindknoten erst in $P_2$ dann in $P_1$ hinzugefügt.

    Die Auswahl des neuen Punktes $p^*$ und die Reihenfolge der Zuordnung entspricht einer Greedy-Strategie: Wir weisen den Punkt der am weitesten entfernt ist erst dem vielversprechendsten Zentrum zu. Falls $r \geq \bar{R}$ werden keine neuen Kinder erzeugt. Es ist sichergestellt, dass die Lösung eines Kindes zwischen $R$ und $r$ eines Elternkonten liegen muss. Der Algorithmus durchwandert den Baum nach den Regeln der Tiefensuche, wobei ein linker Knoten höher priorisierst wird als ein rechter. Tiefensuche bedeutet, dass wir erst die Kinder eines Knotens betrachten bevor wir dessen Nachbarn betrachten.

    Es ist zu beachten, dass in jedem Knoten nur ein 1-Center Problem gelöst werden muss, die anderen $(k-1)$ 1-Center Probleme werden vom Elternknoten vererbt.

    Das 1-Center Problem

    Die Problemstellung

    Das 1-Center Problem entspricht dem $k$-Center Problem mit $k = 1$. Gefragt wird also nach einem Zentrum $c$ eines Containers, der alle Städte (Punkte) $p \in P$ überdeckt. Sei $$\rho(c) = \max_{p \in P}\left|\left| p-c \right|\right|_m,$$ wobei $\left|\left| \cdot \right|\right|_m$ die Distanz unter der Metrik $m$ ist. Wir können zeigen, dass diese Funktion für unsere verwendeten Metriken stetig und konvex ist. Wir fragen somit nach dem Minimum dieser stetig konvexen Funktion.

    • Eingabe: Punkte $P \subset \mathbb{R}^n$
    • Ausgabe: minimale Dilatation $\rho$, Zentrum $c$

    Das Schnittebenenverfahren

    Beim Schnittebenenverfahren starten wir mit einem sehr einfachen linearen Container $H_0$, zum Beispiel mit einem Quadrat $H_0 := \{x : \left|\left|x\right|\right|_\infty \leq 1 \}$. Den linearen Container $H_0$ konstruieren wir aus geeignete Hyperebenen: $x_1 \leq 1, -x_1 \leq 1, x_2 \leq 1, -x_2 \leq 1$. Wir starten das iterative Verfahren mit $i = 0$.

    1. Wir stellen ein lineares Programm $\mathcal{LP}_i$ auf, dessen Bedingungen unseren linearen Container definieren (Variablen sind die Komponenten von $c_i$ und $\rho_i$) und suchen nach einem Zentrum $c_i \in \mathbb{R}^n$ und einer Dilatation $\rho_i$ sodass $$P \subset c_i + H_i \cdot \rho_i.$$ Bemerkung: $c_0 + H_0 \cdot \rho_0 = \{x : || x-c_0 ||_\infty \leq \rho_0 \}$
    2. Wir berechnen eine neue Schnittebene $\nabla \rho(c_i)^Tx$, welche durch den Subgradienten $\nabla \rho(c_i)$ an $c_i$ gegeben ist. Wir schneiden unseren Container $H_i$ mit Schnittebene und erhalten $H_{i+1}$. Wir approximieren dabei die Funktion $\rho(c)$ nahe der optimalen Lösung.
    3. Ist $\frac{\rho(c_i)}{\rho_i} \leq$ Approximationsfaktor, so brechen wir ab, ansonsten gehen wir zu (1).

    Ein Beispiel


    Abbildung 1: Unser euklidischer Container ist $Con = \{x \ : \ \left|\left| x \right| \right|_2 \leq 1\}.$ In grün $Con \cdot \rho(c_0)$ und in rot $Con \cdot \rho_0$, wobei $\rho_0$ aus dem linearen Programm $\mathcal{LP}_0$, errechnet wurde. In blau der linerare Container $c_ 0 + H_0 \cdot \rho_0 := \{x : \left|\left|x-c_0\right|\right|_\infty \leq \rho_0 \}$. Der schwarze erste Schnitt ist durch den Subgradienten $\nabla \rho(c_0)$ definiert.

    Abbildung 2: Erneut in grün $Con \cdot \rho(c_1)$ und in rot $Con \cdot \rho_1$, wobei $\rho_1$ aus dem neuen linearen Programm $\mathcal{LP}_1$ errechnet wurde. Es gilt $H_1 := H_0 \cap \nabla \rho(c_0)^T x$. In blau $c_1 + H_1 \cdot \rho_1$. Der schwarze zweite Schnitt ist durch den Subgradienten $\nabla \rho(c_1)$ definiert.

    Abbildung 3: Erneut in grün $Con \cdot \rho(c_2)$ und in rot $Con \cdot \rho_2$, wobei $\rho_2$ aus dem neuen linearen Programm $\mathcal{LP}_2$ errechnet wurde. Es gilt $H_2 := H_1 \cap \nabla \rho(c_1)^T x$. In blau $c_2 + H_2 \cdot \rho_2$. Der schwarze dritte Schnitt ist durch den Subgradienten $\nabla \rho(c_2)$ definiert.

    Abbildung 4: Weitere Schnitte sind nicht notwendig da $Con \cdot \rho(c_3) = Con \cdot \rho_3.$

    Abbildung 5: Die Approximation ist gut genug und wir können das berechnete Zentrum $c_3$ und $\rho_3$ zurückgeben.

    Abbildung 6: Die Lösung des 1-Center Problems.

    Die Lösung des Dilatationsproblems $\rho(c_i)$ gibt uns, wie so oft eine obere Schranke. Der Schnitt ist stets durch die Hyperebene, welche durch die Normale $\nabla \rho(c_i)$ definiert ist, gegeben. Dabei ist $\nabla \rho(c_i)$ der Subgradient von $\rho$ an der Stelle $c_i$. Die Lösung $\rho_i$ des linearen Programms $\mathcal{LP}_i$ ist eine untere Schranke der optimalen Lösung. Dadurch dass der Subgradient als Schnitt gewählt wird, gilt $Con \subset H_i, \forall i$ und somit schneiden wir niemals zu viel vom linearen Container weg.

    Das Verfahren kann für alle hier verwendeten Metriken benutzt werden, da wir für all diese Metriken einen Subgradienten berechnen können und $\rho$ stetig und konvex ist.

    Ihr Browser unterstützt kein HTML5 Canvas. Bitte verwenden Sie einen modernen Browser, z.B.Mozilla Firefox

    Legende

    Zentrum
    zugewiesener Punkt $p \in P$ ($\exists i: p \in P_i$)
    Punkt $p^*$, der im Knoten hinzugefügt wurde
    nicht zugewiesener Punkt $p \in P$ ($p \notin \bigcup_{i=1}^k P_i$)
    Der äußere Radius ist die lokale obere Schranke $R$ und der innerer die lokale untere Schranke $r$. Die Schranken sind je Zentrum in jedem Knoten gleich eingefärbt.

    Die Anwendung

    Die Anwendung bedient sich des Approximationsalgorithmus, welcher auf Grundlage der Doktorarbeit von Lucia Barbara Roth und der Diplomarbeit von Andreas Arnold, welche beide im Jahre 2009 abgegeben wurden, entwickelt wurde. Die Methoden sind auf dem aktuellem Stand der Forschung. Es ist zu beachten, dass die Einschränkungen in Güte, Anzahl der Zentren und Anzahl der Städte nicht nur aus der Berechnungsdauer für die finale Lösung sondern auch deswegen vorgenommen werden, da die Datenmenge der Berechnungsschritte ab einer gewissen Tiefe des Berechnungsbaumes zu groß wird.

    Schranken

    Obere Schranke

    Angenommen $OPT \in \mathbb{R}$ ist unser Optimale Lösung. Dann git für jede (globale) obere Schranke $R$: $$R \geq OPT$$

    In unserem Berechnungsbaum (Branch&Bound-Baum) ist $R$ eine lokale obere Schranke falls für alle Lösungen $L_i$ aller Kinder $i$ gilt: $$R \geq L_i$$

    Untere Schranke

    Angenommen $OPT \in \mathbb{R}$ ist unser Optimale Lösung. Dann git für jede (globale) untere Schranke $r$: $$r \leq OPT$$

    In unserem Berechnungsbaum (Branch&Bound-Baum) ist $r$ eine lokale untere Schranke falls für alle Lösungen $L_i$ aller Kinder $i$ gilt: $$r \leq L_i$$

    Der Subgradient

    Der Subgradient

    Wir benutzen den Subgradienten um das 1-Center Problem zu lösen. Die Kernidee ist es, dass die optimale Lösung $c$ auf einer uns bekannten Seite der Hyperebene des Subgradienten liegt. Alle anderen Punkte müssen nicht weiter betrachtet werden.

    Sei $\phi : \mathbb{R}^n \to \mathbb{R}$ eine konvexe Funktion. Ein Vektor $g \in \mathbb{R}^n$ is Subgradient von $\phi$ an $c_0$, falls für alle $c \in \mathbb{R}^n$

    $$\phi(c) \geq \phi(c_0) + \langle g, c - c_0 \rangle$$

    gilt, wobei $\langle g, c - c_0 \rangle$ das Skalarprodukt und in unserem Fall gleich $g^T (c - c_0)$ ist. Das Subdifferential $\partial \phi$ an $c_0$ ist die Menge aller Subgradienten von $\phi$ an $c_0$.

    Ein Beispiel

    Sei $\phi : \mathbb{R} \to \mathbb{R}, \phi : c \mapsto \left|c \right|$, dann gilt: $$\partial \phi(c_0) = \begin{cases} \{-1\} & \quad \text{falls } c_0 < 0\\ \left[-1,1\right] & \quad \text{falls } c_0 = 0\\ \{1\} & \quad \text{falls } c_0 > 0\\ \end{cases}$$ subgradient

    Mathestudium an der TUM

    Weitere Approximationsalgorithmen und auch Graphenalgorithmen werden auf der Webseite des Lehrstuhls M9 der TU München erklärt.
    Ein Mathematikstudium an der TU München beantwortet alle weiteren Fragen zur diversen anderen algorithmischen Problemstellungen (sofern eine Lösung bekannt ist).

    Ein letzter Hinweis zum Ziel dieser Seite und zu Zitationen

    Der Lehrstuhl M9 der TU München beschäftigt sich mit diskreter Mathematik, angewandter Geometrie und der Optimierung von mathematischen Problemen. Das hier dargestellte Problem und die zugehörigen Algorithmen ist ein bekanntes Beispiel für die Anwendung von Mathematik auf angewandte Probleme (und ist dem Bereich der kombinatorischen Optimierung zuzuordnen). Diese Seite soll dem Leser dabei helfen, die Anwendung von Mathematik auf lebensnahe Problem zu erkennen und einfache mathematische Lösungsverfahren zu verstehen. Die dargestellten Algorithmen wurden deshalb nach Kriterien der Verständlichkeit und Erklärbarkeit ausgewählt, sie stellen keinesfalls den Forschungsgegenstand des Lehrstuhl dar.

    Um diese Seite zu zitieren, nutze bitte die folgenden Angaben:

    Es ist keine Lösung verfügbar.

    Die Berechnung der Lösung läuft zur Zeit noch. Bitte probiere es in ein paar Sekunden noch einmal!

    Die Berechnung der Lösung wurde abgebrochen. Bitte kehre zum Spiel erstellen-Tab zurück und starte ein neues Spiel.