piwik-script

Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Competitive Location

We investigate a class of location problems where two competing providers place their facilities sequentially and users can decide between the competitors.  We assume that both competitors act non-cooperatively and aim at maximizing their own benefit.  We investigate the complexity and approximability of such problems on graphs, in particular on simple graph classes such as trees and paths. We also develop fast algorithms for single competitive location problems where each provider places one single facilty.

A location problem aims at finding suitable locations for new facilities that are to be opened. Given a set of potential locations, its quality is measured by the distances to the customers of the facilities. Prominent examples are the k-median and the k-center problem. Often, facilities and customers are represented by nodes of an edge-weighted graph. Distances are given by the lengths of shortest paths.

Many location problems dealt with in the literature assume the existence of a single monopolistic provider who wants to open a number of new facilities and looks for a set of good locations. In contrast, competitive location investigates scenarios where two or more competing providers place their facilities and customers can decide between the providers.

We consider models with two sequentially acting competitors, leader and follower. We assume that both competitors offer the same type of good or service at the same price. Hence the user preference can be expressed solely in terms of distances to the locations of the facilities. Every customer chooses the closest competitor. Once the leader has chosen a location, it is the follower's turn to determine a location maximizing his own revenue (the total demand of his customers). Hence the follower's reaction is predictable, which the leader can take into account when making the initial decision. We assume that the competitors act non-cooperatively.

The complexity status of the leader problem on tree graphs has been a long-standing open question (Hakimi, 1990). One of our main results is that the leader problem is NP-hard even on paths thereby answering this question. (For more detailed information we refer to the journal article.) On the positive side we give a fully polynomial-time approximation scheme for paths.

Researchers

Publications

  • A Constant-Factor Approximation Algorithm for Reconciliation \($k$\)-Median. Spoerhase, Joachim; Khodamoradi, Kamyar; Riegel, Benedikt; Ordozgoiti, Bruno; Gionis, Aristides. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS’23), Vol. 206, pp. 1719–1746. {PMLR}, 2023.
  • Independent Set in \($k$\)-Claw-Free Graphs: Conditional \($\chi$\)-Boundedness and the Power of {LP/SDP} Relaxations. Chalermsook, Parinya; Gadekar, Ameet; Khodamoradi, Kamyar; Spoerhase, Joachim. In Proc. International Workshop on Approximation and Online Algorithms (WAOA’23). 2023.
  • Parameterized Approximation Schemes for Clustering with General Norm Objectives. Abbasi, Fateme; Banerjee, Sandip; Byrka, Jaroslaw; Chalermsook, Parinya; Gadekar, Ameet; Khodamoradi, Kamyar; Marx, Daniel; Sharma, Roohani; Spoerhase, Joachim. In Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS’23). 2023.
  • Hypergraph Representation via Axis-Aligned Point-Subspace Cover. Firman, Oksana; Spoerhase, Joachim. In Proc. 16th International Conference and Workshops on Algorithms and Computation (WALCOM’22), Vol. 13174, pp. 328–339. 2022.
  • Approximating the Generalized Minimum {Manhattan} Network Problem. Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander. In Algorithmica, 80(4), pp. 1170–1190. 2018.
  • 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), pp. 620–631. 2018.
  • New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim. In Mathematical Programming, 171(1-2), pp. 433–461. 2018.
  • Approximating Minimum Manhattan Networks in Higher Dimensions. Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen G.; Spoerhase, Joachim; Wolff, Alexander. In Algorithmica, 71(1), pp. 36–52. 2015.
  • Approximating Spanning Trees with Few Branches. Chimani, Markus; Spoerhase, Joachim. In Theory Comput. Syst., 56(1), pp. 181–196. 2015.
  • 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., 18(12), pp. 2583–2592. 2012.
  • 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), pp. 440–450. 2010.
  • Competitive and Voting Location. Technical Report (PhD dissertation), . Spoerhase, Joachim. PhD dissertation. 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, 158(4), pp. 361–373. 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. Spoerhase, Joachim; Wirth, Hans-Christoph. In Information Processing Letters, 109(8), pp. 391–394. 2009.
  • (r,p)-Centroid problems on Paths and Trees. Spoerhase, Joachim; Wirth, Hans-Christoph. In Theoretical Computer Science, 410(47--49), pp. 5128–5137. 2009.
  • 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, 7(2), pp. 256–266. 2009.
  • 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, 181(2), pp. 654–667. 2007.