Document Open Access Logo

The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints

Authors Hung-I Yu, Tien-Ching Lin, Der-Tsai Lee

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.64.pdf
  • Filesize: 457 kB
  • 12 pages

Document Identifiers

Author Details

Hung-I Yu
Tien-Ching Lin
Der-Tsai Lee

Cite As Get BibTex

Hung-I Yu, Tien-Ching Lin, and Der-Tsai Lee. The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.64

Abstract

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and then the follower opens the second. Each customer will patronize the facility closest to him (ties broken in favor of the leader's one), thereby decides the market share of the two players. The goal is to find the best position for the leader’s facility so that his market share is maximized. The best algorithm for this problem is an O(n^2 log n)-time parametric search approach, which searches over the space of possible market share values. 

In the same paper, Drezner also proposed a general version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower's facility is not allowed to be located within a distance R from the leader's. He proposed an O(n^5 log n)-time algorithm for this general version by identifying O(n^4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n^4) candidate points, and present an O(n^2 log n)-time algorithm for the general version, thereby closing the O(n^3) gap between the two bounds.

Subject Classification

Keywords
  • competitive facility
  • Euclidean plane
  • parametric search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aritra Banik, Jean-Lou De Carufel, Anil Maheshwari, and Michiel Smid. Discrete voronoi games and ε-nets, in two and three dimensions. Computational Geometry, 55:41-58, 2016. Google Scholar
  2. Richard Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200-208, January 1987. Google Scholar
  3. Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770-785, 1988. Google Scholar
  4. Abdullah Dasci. Conditional location problems on networks and in the plane. In Horst A. Eiselt and Vladimir Marianov, editors, Foundations of Location Analysis, pages 179-206. Springer US, Boston, MA, 2011. Google Scholar
  5. Ivan Davydov, Yury Kochetov, and Alexandr Plyasunov. On the complexity of the (r|p)-centroid problem in the plane. TOP, 22(2):614-623, 2014. Google Scholar
  6. Zvi Drezner. Competitive location strategies for two facilities. Regional Science and Urban Economics, 12(4):485-493, 1982. Google Scholar
  7. Zvi Drezner and E. Zemel. Competitive location in the plane. Annals of Operations Research, 40(1):173-193, 1992. Google Scholar
  8. Horst A. Eiselt and Gilbert Laporte. Sequential location problems. European Journal of Operational Research, 96(2):217-231, 1997. Google Scholar
  9. Horst A. Eiselt, Gilbert Laporte, and Jacques-Francois Thisse. Competitive location models: a framework and bibliography. Transportation Science, 27(1):44-54, 1993. Google Scholar
  10. Horst A. Eiselt, Vladimir Marianov, and Tammy Drezner. Competitive location models. In Gilbert Laporte, Stefan Nickel, and Francisco Saldanha da Gama, editors, Location Science, pages 365-398. Springer International Publishing, Cham, 2015. Google Scholar
  11. S. Louis Hakimi. On locating new facilities in a competitive environment. European Journal of Operational Research, 12(1):29-35, 1983. Google Scholar
  12. S. Louis Hakimi. Locations with spatial interactions: competitive locations and games. In Pitu B. Mirchandani and Richard L. Francis, editors, Discrete location theory, pages 439-478. Wiley, 1990. Google Scholar
  13. Harold Hotelling. Stability in competition. The Economic Journal, 39(153):41-57, 1929. Google Scholar
  14. D. T. Lee and Y. F. Wu. Geometric complexity of some location problems. Algorithmica, 1(1):193-211, 1986. Google Scholar
  15. Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, October 1983. Google Scholar
  16. Nimrod Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. Google Scholar
  17. Frank Plastria. Static competitive facility location: An overview of optimisation approaches. European Journal of Operational Research, 129(3):461-470, 2001. Google Scholar
  18. Angelika Reiser. A linear selection algorithm for sets of elements with weights. Information Processing Letters, 7(3):159-162, 1978. Google Scholar
  19. D. R. Santos-Peñate, R. Suárez-Vega, and P. Dorta-González. The leader-follower location model. Networks and Spatial Economics, 7(1):45-61, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact