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
-
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces. . In Proc. 51st International Colloquium on Automata, Languages and Programming (ICALP’24). 2024.
-
A Constant-Factor Approximation Algorithm for Reconciliation \($k$\)-Median. . In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS’23), Bd. 206, S. 1719–1746. {PMLR}, 2023.
-
Parameterized Approximation Schemes for Clustering with General Norm Objectives. . In Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS’23). 2023.
-
Independent Set in \($k$\)-Claw-Free Graphs: Conditional \($\chi$\)-Boundedness and the Power of {LP/SDP} Relaxations. . In Proc. International Workshop on Approximation and Online Algorithms (WAOA’23). 2023.
-
Hypergraph Representation via Axis-Aligned Point-Subspace Cover. . In Proc. 16th International Conference and Workshops on Algorithms and Computation (WALCOM’22), Bd. 13174, S. 328–339. 2022.
-
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. . In Mathematical Programming, 171(1-2), S. 433–461. 2018.
-
Approximating the Generalized Minimum {Manhattan} Network Problem. . In Algorithmica, 80(4), S. 1170–1190. 2018.
-
Constant-Factor Approximation for Ordered k-Median. . In Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC’18), S. 620–631. 2018.
-
Approximating Minimum Manhattan Networks in Higher Dimensions. . In Algorithmica, 71(1), S. 36–52. 2015.
-
Approximating Spanning Trees with Few Branches. . In Theory Comput. Syst., 56(1), S. 181–196. 2015.
-
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., 18(12), S. 2583–2592. 2012.
-
Relaxed Voting and Competitive Location under Monotonous Gain Functions on Trees. . In Discrete Applied Mathematics, 158(4), S. 361–373. 2010.
-
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems. . In Proc. 21st International Symposium on Algorithms and Computation (ISAAC’10), S. 440–450. 2010.
-
Competitive and Voting Location. Technical Report (PhD dissertation), . . PhD dissertation. Universität Würzburg, 2010.
-
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, 109(8), S. 391–394. 2009.
-
(r,p)-Centroid problems on Paths and Trees. . In Theoretical Computer Science, 410(47--49), S. 5128–5137. 2009.
-
Optimally Computing all Solutions of {S}tackelberg with Parametric Prices and of General Monotonous Gain Functions on a Tree. . In Journal of Discrete Algorithms, 7(2), S. 256–266. 2009.
-
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, 181(2), S. 654–667. 2007.
