The (1 | 1)-centroid problem in the plane with distance constraints

DOI10.1142/S0218195918600014MaRDI QIDQ3177899zbMATH OpenOpenAlexFDO

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

Publication date 2 August 2018

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

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)

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.

Recommendations

• The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
• A local search heuristic for the \((r| p)\)-centroid problem in the plane
• Improved algorithms for some competitive location centroid problems on paths, trees and graphs
• A new alternating heuristic for the \((r|p)\)-centroid problem on the plane
• VNS heuristic for the \((r|p)\)-centroid problem on the plane

Cites work

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

Cited in

(9)

• No dice: a deterministic approach to the Cartan centroid
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• Improved algorithms for some competitive location centroid problems on paths, trees and graphs
• The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints
• scientific article; zbMATH DE number 5667431 (Why is no real title available?)
• An improvement and an extension of the Elzinga \& Hearn's algorithm to the 1-center problem in \(\mathbb{R}^ n\) with \(l_{2b}\)-norms
• On solving the planar \(k\)-centrum problem with Euclidean distances
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension
• An algorithm and a core set result for the weighted Euclidean one-center problem

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)