Kompetitive Standortprobleme

Wir untersuchen eine Klasse von Standortproblemen, bei denen zwei konkurrierende Anbieter ihre Versorger sequenziell platzieren, und die Kunden sich zwischen den Konkurrenten entscheiden können. Wir nehmen an, dass beide Konkurrenten nicht-kooperativ agieren und auf die Maximierung ihres eigenen Vorteils abzielen. Wir untersuchen die Komplexität und Approximierbarkeit solcher Probleme auf Graphen, insbesondere auf einfachen Graphklassen wie Bäumen und Pfaden. Ferner entwickeln wir schnelle Algorithmen für kompetitive Einzelstandortprobleme, bei denen jeder Anbieter genau einen Versorger errichtet.
Bei einem Standortproblem geht es darum, geeignete Standorte für neu zu errichtende Versorger zu finden. Die Qualität einer Menge von Standorten wird durch ein Qualitätsmaß vorgegeben, das auf den Abständen zu den Kunden der Versorger basiert. Prominente Beispiele sind das k-Median- und das k-Center-Problem. Häufig werden die Standorte und Kunden durch Knoten eines kantengewichteten Graphen repräsentiert. Die Distanzen ergeben sich durch die Längen kürzester Wege.
Viele in der Literatur betrachtete Standortproblem gehen von der Existenz eines einzelnen, monopolistischen Anbieters aus, der eine Anzahl neuer Versorger eröffnen will und dafür eine Menge guter Standorte sucht. Im Gegensatz dazu untersuchen kompetitive Standortprobleme Szenarien in denen zwei oder mehr konkurrierende Anbieter ihre Einrichtungen platzieren und die Kunden sich zwischen den Anbietern entscheiden können.
Wir betrachten Modelle mit zwei sequenziell agierenden Konkurrenten, Leader und Follower. Wir nehmen an, dass beide Konkurrenten das gleiche Gut zum gleichen Preis anbieten. Daher können die Präferenzen der Kunden auf Grundlage der Distanzen zu den Standorten der Versorger formuliert werden. Jeder Kunde wählt den ihm nächstgelegenen Anbieter. Sobald der Leader seine Standorte gewählt hat, ist der Follower in der Lage Standorte zu ermitteln, die seinen Ertrag (die Gesamtnachfrage seiner Kunden) maximieren. Daher ist die Reaktion des Followers vorhersehbar, was der Leader bei seiner anfänglichen Entscheidung berücksichtigen kann. Wir nehmen an, dass beide Konkurrenten nicht-kooperativ agieren.
Der Komplexitätsstatus des Leader-Problems auf Baumgraphen ist eine seit Langem offene Frage gewesen (Hakimi, 1990). Eines unsere Hauptresultate ist, dass das Leader-Problem sogar auf Pfaden NP-schwer ist, wodurch diese Frage beantwortet wird. (Für detailliertere Informationen verweisen wir auf den Journal-Artikel.) Auf der positiven Seite geben wir ein vollpolynomielles Approximationsschema an.
Projektmitarbeiter
- Joachim Spoerhase (bis 2022)
- Hartmut Noltemeier (bis 2010)
- Hans-Christoph Wirth (bis 2010)
Veröffentlichungen
-
Approximating the Generalized Minimum {Manhattan} Network Problem in Algorithmica (2018). 80(4) 1170–1190.
-
Constant-Factor Approximation for Ordered k-Median in Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC’18) (2018). 620–631.
-
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness in Mathematical Programming (2018). 171(1-2) 433–461.
-
Approximating Minimum Manhattan Networks in Higher Dimensions in Algorithmica (2015). 71(1) 36–52.
-
Approximating Spanning Trees with Few Branches in Theory Comput. Syst. (2015). 56(1) 181–196.
-
Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems in Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA’15) (2015).
-
Algorithms for Labeling Focus Regions in IEEE Trans. Vis. Comput. Graph. (2012). 18(12) 2583–2592.
-
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems in Proc. 21st International Symposium on Algorithms and Computation (ISAAC’10) (2010). 440–450.
-
Competitive and Voting Location PhD thesis, Universität Würzburg. (2010).
-
Relaxed Voting and Competitive Location under Monotonous Gain Functions on Trees in Discrete Applied Mathematics (2010). 158(4) 361–373.
-
An {O(n (log n)^2 / log log n)} algorithm for the single maximum coverage location or the {(1,X_p)}-medianoid problem on trees in Information Processing Letters (2009). 109(8) 391–394.
-
(r,p)-Centroid problems on Paths and Trees in Theoretical Computer Science (2009). 410(47--49) 5128–5137.
-
Optimally Computing all Solutions of {S}tackelberg with Parametric Prices and of General Monotonous Gain Functions on a Tree in Journal of Discrete Algorithms (2009). 7(2) 256–266.
-
Approximating (r,p)-centroid on a path in Proc. 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW’08) (2008).
-
Security Score, Plurality Solution, and {N}ash Equilibrium in Multiple Location Problems in 20th European Chapter on Combinatorial Optimization (ECCO’07) (2007).
-
Multiple Voting Location and Single Voting Location on Trees in European Journal of Operational Research (2007). 181(2) 654–667.