piwik-script

English Intern
Lehrstuhl für Informatik I - Algorithmen und Komplexität

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

Veröffentlichungen

  • Approximating the Generalized Minimum {Manhattan} Network Problem Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Algorithmica (2018). 80(4) 1170–1190.
  • Constant-Factor Approximation for Ordered k-Median Byrka, Jaroslaw; Sornat, Krzysztof; Spoerhase, Joachim 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 Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim in Mathematical Programming (2018). 171(1-2) 433–461.
  • Approximating Minimum Manhattan Networks in Higher Dimensions Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen G.; Spoerhase, Joachim; Wolff, Alexander in Algorithmica (2015). 71(1) 36–52.
  • Approximating Spanning Trees with Few Branches Chimani, Markus; Spoerhase, Joachim in Theory Comput. Syst. (2015). 56(1) 181–196.
  • Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems Byrka, Jarosław; Fleszar, Krzysztof; Rybicki, Bartosz; Spoerhase, Joachim in Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA’15) (2015).
  • Algorithms for Labeling Focus Regions Fink, Martin; Haunert, Jan-Henrik; Schulz, Andr{’e}; Spoerhase, Joachim; Wolff, Alexander in IEEE Trans. Vis. Comput. Graph. (2012). 18(12) 2583–2592.
  • An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems Spoerhase, Joachim in Proc. 21st International Symposium on Algorithms and Computation (ISAAC’10) (2010). 440–450.
  • Competitive and Voting Location Spoerhase, Joachim PhD thesis, Universität Würzburg. (2010).
  • Relaxed Voting and Competitive Location under Monotonous Gain Functions on Trees Spoerhase, Joachim; Wirth, Hans-Christoph 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 Spoerhase, Joachim; Wirth, Hans-Christoph in Information Processing Letters (2009). 109(8) 391–394.
  • (r,p)-Centroid problems on Paths and Trees Spoerhase, Joachim; Wirth, Hans-Christoph 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 Spoerhase, Joachim; Wirth, Hans-Christoph in Journal of Discrete Algorithms (2009). 7(2) 256–266.
  • Approximating (r,p)-centroid on a path Spoerhase, Joachim; Wirth, Hans-Christoph 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 Spoerhase, Joachim; Wirth, Hans-Christoph in 20th European Chapter on Combinatorial Optimization (ECCO’07) (2007).
  • Multiple Voting Location and Single Voting Location on Trees Noltemeier, Hartmut; Spoerhase, Joachim; Wirth, Hans-Christoph in European Journal of Operational Research (2007). 181(2) 654–667.