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

    Komplexität und Approximierbarkeit kompetitiver 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 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.
       
    • Algorithms for Labeling Focus Regions. Fink, Martin; Haunert, Jan-Henrik; Schulz, André; 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 (2010). 440-450.
       
    • Competitive and Voting Location. Technical Report (PhD dissertation), Spoerhase, Joachim (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 Stackelberg 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 (2008).
       
    • Security Score, Plurality Solution, and Nash Equilibrium in Multiple Location Problems. Spoerhase, Joachim; Wirth, Hans-Christoph (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.
       
    Kontakt

    Lehrstuhl für Informatik I (Effiziente Algorithmen und wissensbasierte Systeme)
    Am Hubland
    97074 Würzburg

    Tel.: +49 931 31-85054
    E-Mail

    Suche Ansprechpartner

    Hubland Süd, Geb. Z8