The (1|1)-Centroid Problem in the Plane with Distance Constraints

DOI10.1142/S0218195918600014zbMATH Open1397.68211arXiv1608.03680OpenAlexW2884562911MaRDI QIDQ3177899FDOQ3177899

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

Publication date: 2 August 2018

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

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}logn)$-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}logn)$-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}logn)$-time algorithm for the general version, thereby close the $O(n^3)$ gap between the two bounds.

Full work available at URL: https://arxiv.org/abs/1608.03680

zbMATH Keywords

parametric searchEuclidean planecompetitive facility

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Applications of game theory (91A80) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Competitive Location Models: A Framework and Bibliography
• On locating new facilities in a competitive environment
• On the complexity of the \((r|p)\)-centroid problem in the plane
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Parallel Merge Sort
• Static competitive facility location: an overview of optimisation approaches.
• The leader-follower location model
• Sequential location problems
• Conditional Location Problems on Networks and in the Plane
• Geometric complexity of some location problems
• Competitive location in the plane
• Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions
• A linear selection algorithm for sets of elements with weights

Cited In (8)

• Title not available (Why is that?)
• The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
• An improvement and an extension of the Elzinga \& Hearn's algorithm to the 1-center problem in \(\mathbb{R}^ n\) with \(l_{2b}\)-norms
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• On solving the planar \(k\)-centrum problem with Euclidean distances
• No dice: a deterministic approach to the Cartan centroid
• An algorithm and a core set result for the weighted Euclidean one-center problem
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

This page was built for publication: The (1|1)-Centroid Problem in the Plane with Distance Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177899)