Das p-Center-Problem verständlich erklärt

Ein Landkreis will Rettungswachen bauen. Niemand soll zu lange auf Hilfe warten, auch das abgelegenste Dorf nicht. Die Seite zeigt, wie man dafür Standorte wählt, welche einfache Regel ein Versprechen mitbringt und wie viel davon in Messungen übrig bleibt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Das abgelegenste Dorf

Ein Landkreis hat viele Dörfer und will einige Rettungswachen bauen. Jedes Dorf wird von der nächsten Wache aus versorgt. Wo sollen die Wachen stehen?

Das hängt davon ab, was zählt. Möglichkeit eins: Alle Anfahrten zusammen sollen möglichst kurz sein. Möglichkeit zwei: Die längste Anfahrt soll möglichst kurz sein. Dann zählt nur das Dorf, das am weitesten von seiner Wache entfernt liegt. Dieses Dorf heißt hier das Schlusslicht.

Die zweite Aufgabe heißt p-Center-Problem. Das p steht für die Zahl der Wachen.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser. Am Ende dieses Teils gibt es zwei Knöpfe: Der erste öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie das Programm nicht. Seine Karten sind künstlich erzeugt. Die Entfernungen sind Luftlinie, und eine Wache darf nur in einem Dorf stehen. Die Aussagen in diesem Teil beschreiben solche Karten, nicht einen echten Landkreis.

Gesamtstrecke oder Schlusslicht

Die beiden Möglichkeiten führen zu verschiedenen Plänen. Beim Plan mit kürzester Gesamtstrecke darf ein Dorf weit draußen bleiben. Man kann es sich so vorstellen: Eine einzige weite Fahrt zählt in der Summe nicht mehr als viele kleine Ersparnisse bei den anderen Dörfern.

Das Programm enthält dazu eine kleine, eigens gebaute Karte mit neun Dörfern und zwei Wachen. Beim Plan mit kürzester Gesamtstrecke ist dort die längste Anfahrt mehr als doppelt so lang wie beim besten Plan für das Schlusslicht. Das ist ein gebautes Extrem. Wie es im Durchschnitt aussieht, steht bei den Missverständnissen.

Eine einfache Regel: immer zum Schlusslicht

Wie findet man gute Standorte? Eine einfache Regel heißt Farthest-first, auf Deutsch: Weitester zuerst. Sie arbeitet in Schritten.

• Start. Ein frei gewähltes Dorf bekommt die erste Wache.
• Weiter. Man sucht das Dorf, das von allen bisherigen Wachen am weitesten entfernt liegt. Es bekommt die nächste Wache.
• Ende. Das wiederholt man, bis alle Wachen stehen.

Die Regel ist naheliegend: Das Dorf mit der längsten Anfahrt ist genau das, was man verbessern will. Sie entscheidet aber Schritt für Schritt und nimmt keine Wache zurück.

Das Versprechen: höchstens das Doppelte

Für die Regel gibt es ein Versprechen. Stehen die Wachen in Dörfern und sind die Entfernungen echte Luftlinie, ist ihre längste Anfahrt nie mehr als das Doppelte der längsten Anfahrt der bestmöglichen Aufstellung. Das Programm rundet die Entfernungen ab. Dabei kann es die Grenze um eine winzige Spanne überschreiten. Auf den geprüften Karten geschah das nicht. Warum es gilt, zeigt der folgende Gedankengang.

Die Regel hat alle Wachen gesetzt. Das Schlusslicht-Dorf liegt noch eine bestimmte Strecke von seiner Wache entfernt. Nennen wir sie die Schlussstrecke. Jede Wache kam in das Dorf, das damals am weitesten von den früheren Wachen lag. Das war mindestens so weit wie die Schlussstrecke, denn die längste Anfahrt wird mit jeder Wache kürzer, nie länger. Nehmen Sie nun alle Wachen und dazu das Schlusslicht-Dorf. Das ist genau eine Stelle mehr als Wachen, und je zwei dieser Stellen liegen mindestens eine Schlussstrecke auseinander.

Nun denken Sie sich die bestmögliche Aufstellung. Sie hat gleich viele Wachen, also eine weniger als diese Stellen. Es ist wie bei Gästen und Stühlen: Gibt es einen Gast mehr als Stühle, müssen sich zwei Gäste einen Stuhl teilen. Hier gehören also zwei der Stellen zur selben Wache der bestmöglichen Aufstellung. Läuft man von der einen Stelle über diese Wache zur anderen, ist das nie kürzer als der gerade Weg. Beide Wege zusammen sind also mindestens eine Schlussstrecke lang, und der längere davon mindestens eine halbe. Die beste Aufstellung hat deshalb eine längste Anfahrt von mindestens einer halben Schlussstrecke. Unsere ist höchstens doppelt so lang.

Was vom Versprechen übrig bleibt

Das Programm hat die Regel an 40 künstlichen Karten mit je 50 zufällig verteilten Dörfern und fünf Wachen geprüft. Im Mittel lag ihre längste Anfahrt gut vierzig Prozent über der bestmöglichen. Sie traf die bestmögliche Aufstellung auf keiner dieser Karten genau, und das Versprechen wurde auf keiner verletzt.

Nachbessern durch Tauschen

Man kann das Ergebnis verbessern. Dazu tauscht man probehalber eine Wache gegen ein anderes Dorf und behält den Tausch, wenn die längste Anfahrt kürzer wird. Das wiederholt man, bis kein Tausch mehr hilft. Fachleute nennen das Swap-Lokalsuche.

Dabei hilft ein Kniff. Oft ändert ein Tausch die längste Anfahrt nicht. Vermutlich bestimmt dann ein einziges Dorf sie, das der Tausch nicht berührt. Bei gleicher längster Anfahrt entscheidet dann die Gesamtstrecke. Ohne diese zweite Regel bleibt die Suche dort stehen.

Im Mittel über die 40 Karten lag das Ergebnis dann weniger als fünf Prozent über der bestmöglichen Aufstellung. Ohne die zweite Regel lag es gut zwölf Prozent darüber. Sie kann aber stecken bleiben: Auf einer kleinen gebauten Karte hilft kein einzelner Tausch, obwohl es eine bessere Aufstellung gibt.

Häufige Missverständnisse

• „Wer das Schlusslicht schützt, zahlt hohe Gesamtkosten.“ Im Mittel über die 40 Karten stimmte das nicht. Auf jeder Karte hat Plan A die kürzeste Gesamtstrecke, Plan B die kürzeste längste Anfahrt. B hatte im Mittel knapp acht Prozent mehr Gesamtstrecke als A. Dafür war die längste Anfahrt von A im Mittel gut ein Viertel länger als die von B. Das gebaute Extrem von oben kam auf diesen 40 Karten nicht vor.
• „Die Regel ist festgelegt, also ist der Anfang egal.“ Doch: Von welchem Dorf man beginnt, ändert das Ergebnis. Die erste Wache bestimmt, welches Dorf danach das am weitesten entfernte ist, und so ändert sich die ganze Kette. Im Mittel über die 40 Karten lag das Ergebnis beim besten Startdorf knapp zwanzig Prozent über der bestmöglichen Aufstellung, beim schlechtesten gut sechzig Prozent.
• „Ein einzelnes abgelegenes Dorf wirft alles um.“ Dazu wurden 20 Karten mit je vier Wachen ohne und mit einem zusätzlichen Dorf weit außerhalb gerechnet. Die längste Anfahrt der besten Aufstellung stieg im Mittel um gut ein Viertel, weil das Dorf sie direkt bestimmt. Die kürzeste Gesamtstrecke stieg um zwölf Prozent, weil das Dorf dort nur einen Teil beiträgt.

Woran Sie das im Alltag erkennen

• Eine Zusage wie „Hilfe in höchstens dieser Zeit“ meint das Schlusslicht. Ein Versprechen mit „durchschnittlich“ meint die Summe. Beide führen meist zu verschiedenen Standorten.
• Wer ein Familientreffen plant und zuerst fragt, wer die weiteste Anreise hat, geht vor wie die einfache Regel.
• Wer etwas durch kleine Tausche verbessert, etwa Möbel umstellt, hört auf, wenn kein Tausch mehr hilft. Daraus folgt nicht, dass es keine bessere Anordnung gibt.

Wie ernst sind diese Beispiele zu nehmen?

Die Karten sind künstlich, die Entfernungen Luftlinie, und es gibt weder verschieden große Dörfer noch Wachen, die ausfallen. Die Zahlen gelten für solche Karten, nicht für einen echten Landkreis.

Was Sie mitnehmen

• Bei einem Höchstwert entscheidet ein einziger Ort. Fragen Sie, welcher es ist und was es kostet, ihn zu verbessern.
• Ein Versprechen der Art „höchstens das Doppelte“ ist eine Obergrenze und keine Erwartung, und sie gilt nur unter ihren Voraussetzungen. Fragen Sie, wie weit die Praxis darunter liegt.
• Fragen Sie bei jedem Ergebnis, von welchem Anfang es kam und ob andere Anfänge verglichen wurden.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er behandelt das Vertex-p-Center-Problem (Minimax-Standortplanung): Statt einer Summe zählt der größte Abstand. Das passt zu Aufgaben mit einer Erreichbarkeitsgarantie („niemand ist weiter als eine feste Entfernung entfernt“), etwa bei Notdiensten.

• Modell: \(n\) Punkte mit Abständen \(d_{ij}\). Gewählt werden \(p\) Punkte als Mittelpunkte; jeder Punkt geht zum nächsten Mittelpunkt. Die Mittelpunkte sind Punkte der Menge (Vertex-p-Center). Es gibt keine Kapazitäten, keine Gewichte und keinen Ausfall von Mittelpunkten.
• Abstände: Luftlinie, in Zehntel-Einheiten ganzzahlig abgerundet. Damit sind alle Radien und Summen ganze Zahlen; angezeigt werden sie durch 10 geteilt (Karteneinheiten, also die Einheit der Koordinaten).
• Netze: erzeugte Zufallsnetze (gleichverteilt oder in vier Clustern) bis 80 Punkte auf einer quadratischen Karte mit ganzzahligen Koordinaten von null bis neunundneunzig (Angabe aus dem Code der Demo, nicht aus der Beschreibung). Voreinstellung sind 50 gleichverteilte Punkte mit \(p=5\). Optional kommt ein Ausreißer bei (150, 150) hinzu, weit außerhalb der Karte. Fremddaten gibt es nicht.
• Lehrnetze: drei kleine, von Hand konstruierte Punktmengen mit ganzzahligen Koordinaten, an denen sich je ein Effekt nachrechnen lässt. „Garantie“ (7 Punkte, \(p=2\)): Farthest-first erreicht das Doppelte des Optimums. „Steckt fest“ (8 Punkte, \(p=3\)): die Swap-Lokalsuche findet keinen verbessernden Tausch. „Summe gegen Maximum“ (9 Punkte, \(p=2\)): p-Center- und p-Median-Optimum unterscheiden sich stark.
• Verfahren: Farthest-first mit wählbarem Startpunkt (Gleichstand: kleinster Index), Swap-Lokalsuche, das exakte Optimum (Binärsuche über den Radius, Überdeckungsproblem als gemischt-ganzzahliges lineares Programm), das p-Median-Optimum zum Vergleich und für \(p=1\) der kleinste umschließende Kreis.
• Maß: Die Güte eines Verfahrens ist das Verhältnis seines Radius zum exakt berechneten Optimalradius, kurz „\(x\)-fach“. „Im Mittel“ ist der Mittelwert über feste Zufallsnetze (40 Netze für die Verteilungen, 20 Netze je \(p\) für die Reihe über \(p\)); „schlechtestes Netz“ ist das größte Verhältnis dieser Netze. Wegen der unterschiedlichen Stichproben weichen Mittelwerte für dasselbe \(p\) leicht ab.

Die Formeln

Gegeben sind die Punktmenge \(V\) mit \(|V|=n\) und die Abstände \(d_{ij}\). Für eine Auswahl \(S\subseteq V\) mit \(|S|=p\) ist der Radius der größte Abstand eines Punkts zum nächsten Mittelpunkt; gesucht ist der kleinste Radius \(r^*=\min_S r(S)\):

\[r(S)=\max_{j\in V}\min_{i\in S}d_{ij}\]

Der Optimalradius ist einer der Abstände. Für einen Radius \(r\) sei \(N_r(j)=\{i:d_{ij}\le r\}\) die Menge der Punkte, die einen Punkt \(j\) überdecken, und \(y_i=1\), wenn \(i\) Mittelpunkt ist. Die kleinste Zahl \(k(r)\) von Mittelpunkten, mit der jeder Punkt höchstens den Abstand \(r\) von einem Mittelpunkt hat (Überdeckungsproblem), ist:

\[k(r)=\min\Big\{\sum_iy_i:\ \sum_{i\in N_r(j)}y_i\ge1\ \forall j,\ y\in\{0,1\}^V\Big\}\]

\(k(r)\) fällt mit wachsendem \(r\). Also ist \(r^*=\min\{r:k(r)\le p\}\), und eine Binärsuche über die sortierten Abstände findet es. Ein Radius \(r\) ist zulässig, wenn \(k(r)\le p\) gilt. Lässt man statt der Werte null und eins auch alle Werte dazwischen für \(y_i\) zu (LP-Relaxation, ein lineares Programm ohne Ganzzahligkeit), kann der Zielwert nur kleiner werden. Der kleinste Radius, für den dieser LP-Wert höchstens \(p\) beträgt, heißt LP-Radius und ist eine Untergrenze des Optimalradius.

Farthest-first. Mit einem Startpunkt \(s\) ist \(S_1=\{s\}\), und jeder Schritt nimmt den Punkt mit dem größten Abstand zur bisherigen Menge hinzu: \(S_{t+1}=S_t\cup\{\arg\max_j d(j,S_t)\}\) mit \(d(j,S_t)=\min_{i\in S_t}d_{ij}\). Nach \(p\) Schritten ist der Radius \(r_p=r(S_p)\).

Swap-Lokalsuche. Nachbarschaft: einen Mittelpunkt gegen einen Nichtmittelpunkt tauschen. In jedem Schritt wird der beste Tausch ausgeführt, solange das Paar (Radius, Summe der Abstände zum nächsten Mittelpunkt) lexikografisch sinkt, das heißt: erst zählt der Radius, nur bei gleichem Radius die Summe; Gleichstand: kleinster Index. Die Variante „nur Radius“ vergleicht allein den Radius. Ein Plateau ist hier eine Menge von Auswahlen, die denselben Radius haben; ohne die Summe zeigt auf ihm kein Tausch eine Verbesserung.

Preis der Fairness. Als Vergleich dient das p-Median-Problem, das die Summe statt des Maximums minimiert:

\[\min_S\sum_j\min_{i\in S}d_{ij}\]

Der Preis der Fairness ist \(r(S_{\text{Median}})/r^*\) für die Median-Lösung und \(\text{Summe}(S_{\text{Center}})/\text{Summe}^*\) für die Center-Lösung, wobei \(\text{Summe}^*\) die kleinste Summe, also die der p-Median-Lösung ist; als Center-Lösung gilt unter den Auswahlen mit optimalem Radius die mit der kleinsten Summe.

Herleitung der Garantie 2

Das Argument geht auf Gonzalez (1985) zurück; die Ausführung hier ist eine Rechnung dieser Seite, keine Messung der Demo. Sei \(c_1,\dots,c_p\) die Reihenfolge der Mittelpunkte und \(r_t\) der Radius nach \(t\) Mittelpunkten, \(f\) der am weitesten entfernte Punkt nach \(p\) Schritten. Die Herleitung gilt für eine echte Metrik; die Abweichung durch das Abrunden steht danach.

• Schritt 1: Ein weiterer Mittelpunkt kann den Radius nicht erhöhen, also ist \(r_t\ge r_p\) für alle \(t\le p\).
• Schritt 2: Der Mittelpunkt \(c_{t+1}\) ist der Punkt mit dem größten Abstand zu \(c_1,\dots,c_t\), und dieser Abstand ist \(r_t\). Daher hat \(c_{t+1}\) zu jedem früheren Mittelpunkt mindestens den Abstand \(r_t\ge r_p\). Ebenso hat \(f\) zu jedem \(c_i\) mindestens den Abstand \(r_p\).
• Schritt 3: Die \(p+1\) Punkte \(c_1,\dots,c_p,f\) sind also paarweise mindestens \(r_p\) voneinander entfernt. Ordnet man in einer optimalen Auswahl jeden dieser Punkte seinem nächsten optimalen Mittelpunkt zu, teilen sich nach dem Schubfachprinzip zwei Punkte \(a,b\) einen Mittelpunkt \(w\).
• Schritt 4: Mit der Dreiecksungleichung gilt \(r_p\le d(a,b)\le d(a,w)+d(w,b)\le 2r^*\). Der Radius von Farthest-first ist also höchstens doppelt so groß wie der Optimalradius, von jedem Startpunkt aus.

Bedingungen und Grenzen: Der Beweis verwendet die Dreiecksungleichung. Die auf Zehntel abgerundeten Abstände der Demo erfüllen sie nur bis auf eine Einheit, denn die Summe zweier abgerundeter Abstände kann um eine Einheit kleiner sein als der abgerundete Abstand der Summe. Streng folgt daraus nur die Schranke \(2r^*\) plus eine Einheit (Rechnung dieser Seite). Sie wird mit den abgerundeten Abständen tatsächlich verfehlt, aber um höchstens eine Einheit: Eine Suche über kleine Zufallsnetze mit den Abstandsregeln der Demo fand Fälle, in denen der Farthest-first-Radius eine Einheit über dem Doppelten des Optimalradius liegt, schon bei sechs Punkten und \(p=2\) (Rechnung dieser Seite, keine Messung der Demo). Beispiel mit den Punkten (zehn, fünfzehn), (elf, sechzehn), (neun, zwei), (acht, neunzehn), (zehn, drei) und (zwölf, elf), Start beim dritten Punkt: Farthest-first endet bei neunundachtzig Zehntel-Einheiten, das Optimum liegt bei vierundvierzig, und neunundachtzig liegt über achtundachtzig, dem Doppelten von vierundvierzig. In allen gemessenen Netzen der Demo wurde \(2r^*\) nicht überschritten. Für echte Luftlinie gilt die Garantie 2 ohne Zusatz. Dass die Schranke 2 erreicht werden kann, zeigt das Lehrnetz „Garantie“ im nächsten Abschnitt. Für beliebige Metriken ist unter \(P\ne NP\) keine bessere Näherung als 2 möglich (Hsu und Nemhauser, laut der Quelle der Demo). Für die euklidische Ebene, in der die Demo rechnet, ist nach dem Gedächtnis dieser Seite nur eine etwas kleinere Härteschranke bekannt (Feder und Greene, nicht geprüft); ob 2 dort die Grenze ist, lässt diese Seite offen.

Durchgerechnetes Beispiel

Voraussetzung: 50 gleichverteilte Punkte, \(p=5\), Farthest-first ab Punkt 1. Die Radien nach 1 bis 5 Mittelpunkten sind 96,8 / 81,6 / 65,0 / 48,6 / 42,6, der Optimalradius ist 28,4; Farthest-first liegt also beim 1,50-Fachen. Die Radien fallen von Schritt zu Schritt, wie Schritt 1 der Herleitung verlangt. Der Endradius liegt unter der Obergrenze, dem Doppelten des Optimalradius (Rechnung dieser Seite).

Jeder Zwischenradius \(r_t\) begrenzt nach der Herleitung nur den Optimalradius für \(t\) Mittelpunkte nach unten (auf die Hälfte von \(r_t\)), nicht den für fünf. Die Untergrenze für \(p=5\) liefert allein der Endradius.

Die Schranke wird erreicht: Im Lehrnetz mit 7 Punkten und \(p=2\) endet Farthest-first ab Punkt 1 bei 16,0, das Optimum {Punkt 3, Punkt 6} hat den Radius 8,0, also genau das Doppelte.

Befunde

Voraussetzungen: Standardnetz mit 50 gleichverteilten Punkten und \(p=5\), Farthest-first ab Punkt 1, soweit nicht anders genannt. Verhältnisse („\(x\)-fach“) beziehen sich auf den exakt berechneten Optimalradius, außer wo die Zeile etwas anderes nennt (Summen, Ausreißer, Kreis).

Frage	Befund
Standardnetz: Radien	Optimalradius 28,4 (der LP-Radius ebenfalls). Swap-Lokalsuche ab dem Farthest-first-Ergebnis endet bei 32,6 (4 Züge, Summe 843,9), nur mit dem Radius ebenfalls bei 32,6 (2 Züge).
Standardnetz: Startpunkt	Der beste Startpunkt (Punkt 25) liefert 36,0, der schlechteste (Punkt 22) 48,6.
Standardnetz: Summe gegen Maximum	p-Median-Lösung: Summe 795,9, Radius 35,3. p-Center-Lösung mit der kleinsten Summe unter den Radius-Optima: Summe 856,2.
Wie weit unter der Garantie 2? (40 gleichverteilte Netze, \(p=5\))	Farthest-first im Mittel 1,415-fach (Zwischenwert im statistischen Sinn 1,441, schlechtestes Netz 1,718), nie exakt. Bester Start je Netz 1,199-fach (schlechtestes 1,458), ebenfalls nie exakt. Schlechtester Start 1,633-fach (bis 1,804). Die Garantie 2 wird in keinem Netz verletzt.
Dasselbe in 40 Clusternetzen (\(p=4\))	Farthest-first 1,491-fach (bis 1,826), bester Start 1,293, schlechtester 1,665 (bis 1,923).
Swap-Lokalsuche (40 gleichverteilte Netze)	Mit Summe als zweitem Schlüssel 1,045-fach (schlechtestes 1,196, exakt in 15 Netzen, im Mittel 7,1 Züge), nur mit dem Radius 1,120-fach (schlechtestes 1,357, exakt in 8 Netzen, 3,7 Züge). In den Clusternetzen 1,021 (exakt in 30) gegen 1,141 (exakt in 17).
Swap-Lokalsuche im Einzelfall	Cluster-Beispiel mit 50 Punkten, \(p=4\), Optimalradius 16,1: mit Summe endet die Suche bei 18,6, nur mit dem Radius bei 16,1. Lehrnetz mit 8 Punkten und \(p=3\): Farthest-first endet bei 10,0, kein einzelner Tausch senkt Radius oder Summe, das Optimum ist 6,0.
Preis der Fairness (40 gleichverteilte Netze)	Die p-Median-Lösung hat im Mittel den 1,276-fachen Optimalradius (schlechtestes Netz 1,614); die p-Center-Lösung hat die 1,079-fache Summe (schlechtestes 1,187). Lehrnetz mit 9 Punkten und \(p=2\): p-Center Radius 9,2 bei Summe 46,8, p-Median Summe 37,5 bei Radius 19,6 (2,13-fach).
Überdeckungs-LP	Der LP-Radius trifft den Optimalradius in 40 von 40 gleichverteilten und 40 von 40 Clusternetzen.
Ausreißer (\(p=4\), 20 Netze)	Ein zusätzlicher Punkt bei (150, 150): Der Optimalradius steigt im Mittel auf das 1,251-Fache (1,122 bis 1,380), die p-Median-Kosten auf das 1,120-Fache (1,097 bis 1,154). Einzelnetz mit 51 Punkten: Optimalradius 41,1, Farthest-first 65,0, Swap mit Summe 41,1, nur mit dem Radius 47,4.
Mittelpunkt frei statt auf einem Punkt (\(p=1\), 40 Netze)	Der beste Punkt als Mittelpunkt hat im Mittel den 1,073-fachen Radius des kleinsten umschließenden Kreises (größtes Verhältnis 1,171; das kleinste, 0,999, entsteht nur durch das Abrunden).

Reihe über die Zahl der Mittelpunkte (gleichverteilte Netze, 20 Netze je \(p\), Mittelwerte). Die Spalten Farthest-first und Radius der p-Median-Lösung sind Verhältnisse zum Optimalradius, die Spalte „Summe der p-Center-Lösung“ ist ein Verhältnis zur kleinsten Summe (der p-Median-Lösung):

\(p\)	Farthest-first, Start Punkt 1	Farthest-first, bester Start	Radius der p-Median-Lösung	Summe der p-Center-Lösung	LP-Radius exakt in
1	1,495	1,000	1,045	1,008	20 von 20
2	1,407	1,151	1,185	1,057	20 von 20
3	1,482	1,148	1,217	1,049	20 von 20
5	1,446	1,215	1,271	1,074	20 von 20
8	1,372	1,163	1,347	1,073	19 von 20

Was die Messung zeigt und wo sie endet

• Garantie und Praxis: Die Garantie 2 ist eine Obergrenze. In den gemessenen Netzen liegt Farthest-first ab Punkt 1 im Mittel bei etwa 1,4 bis 1,5; je nach Startpunkt reichen die Mittelwerte von etwa 1,2 (bester Start) bis etwa 1,6 (schlechtester Start). Das gilt für die erzeugten Netze; ob es für andere Punktverteilungen genauso ist, zeigt die Messung nicht.
• Startpunkt: Der Abstand zwischen bestem und schlechtestem Startpunkt ist in den Mittelwerten größer als der Abstand des besten Starts zum Optimum. Der Startpunkt ist für diese Netze also nicht nebensächlich.
• Swap-Lokalsuche: Der zweite Schlüssel Summe hilft im Mittel, weil sonst auf Plateaus des Radius kein Tausch eine Verbesserung zeigt. Es gibt keinen einheitlichen Gewinner: im Cluster-Beispiel liefert der Radius allein das Optimum und die Variante mit Summe nicht. Auf dem Lehrnetz „steckt fest“ bleibt die Suche in beiden Varianten stehen.
• Überdeckungs-LP: Dass der LP-Radius das Optimum in fast allen gemessenen Fällen trifft (die eine Ausnahme liegt bei \(p=8\)), ist eine Eigenschaft dieser Netze. Im Allgemeinen ist er nur eine Untergrenze, und das exakte Rechnen ist im Allgemeinen NP-schwer (unter \(P\ne NP\) gibt es kein Verfahren, dessen Rechenzeit nur polynomiell mit der Netzgröße wächst); die Binärsuche mit Überdeckungs-MILP löst alle Netze bis 80 Punkte.
• Ausreißer: Der Optimalradius reagiert stärker als die p-Median-Kosten, weil der Ausreißer ihn direkt bestimmt, aber beide Faktoren liegen nahe beieinander (Zahlen in der Tabelle). Der Unterschied hängt von der Lage ab: Eine Vorprüfung mit dem Ausreißer bei (250, 250) ergab für den Optimalradius 1,27 gegen 1,19 für die p-Median-Kosten.
• Preis der Fairness: Er ist im Mittel mäßig und geht in beide Richtungen: Der Schutz des Weitesten kostet etwas Gesamtstrecke, der Schutz der Summe etwas mehr Radius. Die großen Werte stammen aus dem konstruierten Lehrnetz und nicht aus den Zufallsnetzen; im schlechtesten Zufallsnetz liegt der Radius der Median-Lösung unter dem Doppelten (Tabelle).
• Nicht gezeigt: freie Mittelpunkte für \(p>1\) (nur der Kreis für \(p=1\)), Kapazitäten, Gewichte (Nachfragen), Straßennetze und Fahrzeiten, Ausfälle von Mittelpunkten, Fremddaten.

Quellen

• Gonzalez, T. F. (1985): Clustering to minimize the maximum intercluster distance. Theoretical Computer Science 38.
• Hsu, W.-L.; Nemhauser, G. L. (1979): Easy and hard bottleneck location problems. Discrete Applied Mathematics 1.
• Welzl, E. (1991): Smallest enclosing disks (balls and ellipsoids). In: New Results and New Trends in Computer Science, LNCS 555.
• Hochbaum, D. S.; Shmoys, D. B. (1985): A best possible heuristic for the k-center problem. Mathematics of Operations Research 10 (dieselbe Regel unabhängig gefunden).
• Feder, T.; Greene, D. H. (1988): Optimal algorithms for approximate clustering. STOC 1988 (Härteschranke für die Ebene).

Autor und Jahr von Gonzalez, Hsu/Nemhauser und Welzl stehen in der Quelle der Demo; alle Titel und Fundstellen sowie die beiden letzten Einträge sind aus dem Gedächtnis ergänzt und nicht geprüft.