Competitive and voting location [Elektronische Ressource] / Joachim Spoerhase

Sujets

• Informatik

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2010
• Nombre de lectures: 18
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Julius-Maximilians-Universität Würzburg
Fakultät für Mathematik und Informatik
Dissertation
Competitive and Voting Location
Joachim Spoerhase
October 2010
Supervisor: Prof. Dr. Hartmut Noltemeier
Referees: Prof. Dr. Hartmut Noltemeier
Prof. Dr. Alexander Wolff
Prof. Dr. Horst A. EiseltZusammenfassung
Gegenstand dieser Arbeit sind bestimmte Klassen von Standortproblemen.
Bei einem Standortproblem geht es darum, einen geeigneten Standort
für eine neu zu eröffnende Einrichtung zu finden. Beispiele für solche
Einrichtungen sind Geschäfte, Warenlager, Fabriken, Krankenhäuser, aber
auch Server in einem Computer-Netzwerk. Welche Standorte geeignet
sind, wird durch ein numerisches Qualitätsmaß vorgegeben, das auf den
Abständen des jeweiligen Standorts zu den Kunden oder Benutzern der
Einrichtung beruht. Aufgrund der Vielzahl möglicher Anwendungen gibt
es verschiedenste Arten solcher Qualitätsmaße.
In dieser Arbeit werden zwei Klassen von Standortproblemen, soge-
nannte kompetitive Standortprobleme und Voting-Standortprobleme, unter-
sucht. Im Folgenden werden beide Problemklassen kurz dargestellt.
Für viele in der Fachliteratur betrachtete Standortprobleme unterstellt
man einen einzelnen, monopolistischen Anbieter, der einen Standort für
eine neu zu eröffnende Einrichtung sucht. Im Gegensatz dazu geht man
bei kompetitiven Standortproblemen von zwei oder mehr Anbietern aus, die
um Kundschaft konkurrieren. Die vorliegende Arbeit konzentriert sich auf
Modelle mit genau zwei Wettbewerbern, genannt Leader und Follower. Es
wird angenommen, dass diese Anbieter ähnliche Produkte zu ähnlichen
Preisen anbieten. Aus Sicht der Kunden unterscheiden sich die Anbieter
dann lediglich durch ihre Standorte. Jeder Kunde wählt den ihm nächstge-
legenen Anbieter. Die Platzierung der Einrichtungen von Leader und Fol-
lower erfolgt sequentiell: Zunächst wählt der Leader seinen Standort. Die
Kenntnis dieses Standorts ermöglicht es dem Follower, einen Standort für
seine Einrichtung zu bestimmen, der seinen eigenen Ertrag (Gesamtbedarf
seiner Kunden) maximiert. Dadurch wird das Verhalten des Followers für
den Leader vorhersehbar, was dieser bei seiner initialen Entscheidung be-
rücksichtigen kann, um einen für ihn optimalen Standort zu finden. In den
hier betrachteten Modellen agieren die Wettbewerber rein eigennützig.
Bei Voting-Standortproblemen geht es hingegen um soziale Gesichtspunk-
te: Ein Anbieter versucht, einen Standort zu bestimmen, der die Benutzer
oder Kunden soweit wie möglich zufrieden stellt. Solche Fragestellungen
sind beispielsweise bei der Planung öffentlicher Einrichtungen relevant.
3In den meisten Fällen gibt es keinen Standort, der von allen Benutzern
favorisiert wird. Daher muss ein Kompromiss gefunden werden. Hierzu
werden Kriterien betrachtet, die auch in Wahlsystemen eingesetzt werden:
Ein geeigneter Standort wird als Sieger einer gedachten Wahl verstanden,
bei der die möglichen Standorte die zur Wahl stehenden Kandidaten und
die Kunden die Wähler darstellen.
Der Zusammenhang zwischen kompetitiven Standortproblemen und
Voting-Standortproblemen besteht darin, dass Standorte, die vorteilhaft
für den Leader im kompetitiven Modell sind, auch gute Kompromisse im
Sinne der Voting-Standortprobleme sind.
Die zentrale Fragestellung dieser Arbeit ist, wie schnell sich kompeti-
tive Standortprobleme und Voting-Standortprobleme algorithmisch lösen
lassen. Als Maß für die Effizienz eines Algorithmus dient seine asympto-
tische Laufzeit. Als Entscheidungsraum werden Graphen verwendet. Das
heißt, die potentiellen Standorte und die Kunden werden durch Knoten
oder Punkte auf Kanten eines Graphen modelliert. Die Abstände zwischen
Kunden und Standorten ergeben sich durch Kürzeste-Wege-Distanzen im
zugrundeliegenden Graphen.
Im Folgenden werden wesentliche Ergebnisse der vorliegenden Arbeit
zusammengefasst.
Im ersten Teil der Arbeit werden relaxierte Einfachstandortprobleme behan-
delt. Bei einem Einfachstandortproblem platziert jeder Anbieter genau eine
Einrichtung. Durch die Relaxierung wird eine gewisse Zurückhaltung der
Kunden modelliert, wie sie in der realen Welt beobachtet werden kann: Ein
Kunde ist erst dann bereit, zu einem neuen Anbieter (Follower) zu wech-
seln, wenn dieser signifikant besser als der bereits existierende ist. Im hier
untersuchten Modell muss dazu die Differenz der Abstände des Kunden
zu Leader bzw. Follower eine vorgegebene Schranke überschreiten.
Zuerst werden monotone Gewinnfunktionen als ein neues und allgemeines
Modell für relaxierte kompetitive Standortprobleme und Voting-Standort-
probleme eingeführt (Kapitel 3). Alle aus der Fachliteratur bekannten Ein-
fachstandortprobleme, die in dieser Arbeit betrachtet werden, lassen sich
durch monotone Gewinnfunktionen beschreiben. Es ergeben sich jedoch
auch neue, bislang noch nicht untersuchte Probleme.
Im ersten Teil der Arbeit werden monotone Gewinnfunktionen vorran-
gig auf Baumgraphen betrachtet. Wir entwickeln einen Linearzeit-Algorith-
mus zur Bestimmung einer optimalen Lösung für eine monotone Gewinn-
funktion auf einem Baum (Kapitel 4).
Das Problem, die Menge aller Lösungen einer monotonen Gewinnfunk-
tion auf einem Baum zu bestimmen, erweist sich als schwieriger (Kapi-
tel 5). Wir beweisen (für bestimmte Rechnermodelle) eine untere Laufzeit-
4schranke von
(n logn), wobein die Anzahl der Knoten im Baum ist. Auf
der anderen Seite wird ein Algorithmus mit einer optimalen Laufzeit von
O(n logn) zur Bestimmung der Lösungsmenge vorgestellt. In bestimmten
Spezialfällen ist sogar lineare Laufzeit möglich. Als Nebenprodukt ergibt
sich ein Linearzeit-Algorithmus für das sogenannte Stackelbergproblem mit
parametrischen Preisen. Dies ist eine wesentliche Verbesserung gegenüber
3dem bekannten Algorithmus mit einer Laufzeit vonO(n logn).
Der zweite Teil der Arbeit befasst sich mit kompetitiven Mehrfachstand-
ortproblemen. Hier platzieren Leader und Follower eine vorgegebene An-
zahl von Einrichtungen. Kompetitive Mehrfachstandortprobleme erwei-
sen sich als wesentlich schwieriger als die entsprechenden Einfachstand-
ortprobleme.
Zunächst wird die Komplexität kompetitiver Mehrfachstandortproble-
me auf allgemeinen Graphen untersucht (Kapitel 7). Wir betrachten das Pro-
blem des Leaders (Leader-Problem), eine optimale Platzierung zu finden,
p
und zeigen, dass das korrespondierende Entscheidungsproblem -voll-
2
ständig ist. Dies verschärft das bekannte NP-Schwere-Resultat und legt
nahe, dass das Leader-Problem schwieriger ist als viele typische, in der
Fachliteratur untersuchte Optimierungsprobleme.
Wir untersuchen auch die Approximierbarkeit kompetitiver Mehrfach-
1-"standortprobleme. Wir geben eine untere Schranke vonn für die Ap-
proximierbarkeit des Leader-Problems an. Diese zeigt, dass es (unter der
Annahme P = NP) keinen Approximationsalgorithmus für das Leader-
Problem gibt, der auch im Worst-Case zufriedenstellend approximiert. Für
das Follower-Problem ergibt sich ein Verfahren mit konstanter Approxi-
mationsgüte. Wir zeigen, dass diese Güte die bestmögliche ist.
In den verbleibenden Kapiteln werden die kompetitiven Mehrfach-
standortprobleme für Bäume und Pfade untersucht.
Der Komplexitätsstatus des Leader-Problems auf Bäumen ist eine seit lan-
gem offene Frage (Hakimi, 1990). Wir zeigen, dass das Leader-Problem so-
gar auf Pfaden NP-schwer ist, was diese Frage somit beantwortet (Kapi-
tel 9). Auf der positiven Seite wird ein vollpolynomielles Approximations-
schema (FPTAS) für Pfade entwickelt. Für verschiedene Spezialfälle des
Leader-Problems auf Bäumen stellen wir effiziente Algorithmen vor oder
beweisen die NP-Schwere.
Für das Follower-Problem auf Bäumen ist bereits ein Polynomialzeit-Algo-
rithmus bekannt. Wir konzentrieren uns auf einen Spezialfall, in dem der
Follower nur eine Einrichtung platziert, der Leader jedoch mehrere (Kapi-
tel 8). Wir entwickeln einen Algorithmus mitO(n logn) Laufzeit, der das
entsprechende Follower-Problem für Bäume löst. Dieser schlägt das bis-
2
lang schnellste Verfahren, welches eine Laufzeit vonO(n log n) hat.
5
6Abstract
The subject of this thesis is the investigation of certain classes of location
problems. A location problem aims at finding a suitable location for a new
facility that is to be opened. Examples for such facilities are shops, ware-
houses, plants, hospitals, but also servers in a computer network. The
adequacy of a location is specified in terms of a given numerical quality
measure that is based on the distances between the respective location and
the customers or users of the facility. Due to the multitude of possible ap-
plications there is also a variety of different quality measures.
This thesis focuses on two classes of location problems: so-called com-
petitive location problems and voting location problems. In the following both
problem classes are briefly described.
Many location problems dealt with in the liter