Top

Journal of Combinatorial Optimization

Published in:

01-03-2023

The two-center problem of uncertain points on a real line

Authors: Haitao Xu, Jingru Zhang

Published in: Journal of Combinatorial Optimization | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Facility location problems on uncertain demand data have attracted significant attention recently. In this paper, we consider the two-center problem on uncertain points on a real line. The input is a set \(\mathcal {P}\) of n uncertain points on the line. Each uncertain point is represented by a probability density function that is a piecewise uniform distribution (i.e., a histogram) of complexity m. The goal is to find two points (centers) on the line so that the maximum expected distance of all uncertain points to their expected closest centers is minimized. A previous algorithm for the uncertain k-center problem can solve this problem in \(O(mn\log mn + n\log ^2n)\) time. In this paper, we propose a more efficient algorithm solving it in \(O(mn\log m+n\log n)\) time. Besides, we give an algorithm of the same time complexity for the discrete case where each uncertain point follows a discrete distribution.

previous article RETRACTED ARTICLE: A novel dynamic en-route and slot allocation method based on receding horizon control

next article The balanced 2-median and 2-maxian problems on a tree

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Agarwal P, Sharir M (1994) Planar geometric location problems. Algorithmica 11:185–195MathSciNetCrossRef

Alipour S (2020) Approximation algorithms for probabilistic \(k\)-center clustering. In: Proceedings of the IEEE international conference on data mining (ICDM), pp 1–11

Alipour S, Jafari A (2018) Improvements on the \(k\)-center problem for uncertain data. In: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, pp 425–433

Averbakh I, Bereg S (2005) Facility location problems with uncertainty on the plane. Discrete Optim. 2:3–34MathSciNetCrossRefMATH

Averbakh I, Berman O (1997) Minimax regret \(p\)-center location on a network with demand uncertainty. Locat. Sci. 5:247–254CrossRefMATH

Banik A, Bhattacharya B, Das S, Kameda T, Song Z (2016) The \(p\)-center problem in tree networks revisited. In: Proceedings of the 15th Scandinavian symposium and workshops on algorithm theory (SWAT), pp 6:1–6:15

Ben-Moshe B, Bhattacharya B, Shi Q (2006) An optimal algorithm for the continuous/discrete weighted \(2\)-center problem in trees. In: Latin American symposium on theoretical informatics, pp 166–177

Bhattacharya B, Shi Q (2007) Optimal algorithms for the weighted \(p\)-center problems on the real line for small \(p\). In: Proceedings of the 10th international workshop on algorithms and data structures, pp 529–540

Chan T (1999) More planar two-center algorithms. Comput Geom Theory Appl 13:189–198MathSciNetCrossRefMATH

Chau M, Cheng R, Kao B, Ngai J (2006) Uncertain data mining: An example in clustering location data. In: Proceedings of the 10th Pacific-Asia conference on advances in knowledge discovery and data mining (PAKDD), pp 199–204

Chazelle B, Guibas L (1986a) Fractional cascading: I. A data structuring technique. Algorithmica 1(1):133–162

Chazelle B, Guibas L (1986b) Fractional cascading: II. Applieacations. Algorithmica 1(1):163–191

Chen D, Wang H (2013) A note on searching line arrangements and applications. Inf Process Lett 113:518–521MathSciNetCrossRefMATH

Chen D, Li J, Wang H (2015) Efficient algorithms for the one-dimensional \(k\)-center problem. Theor Comput Sci 592:135–142MathSciNetCrossRefMATH

Cole R (1987) Slowing down sorting networks to obtain faster sorting algorithms. J ACM 34(1):200–208MathSciNetCrossRefMATH

Eppstein D (1997) Faster construction of planar two-centers. In: Proceedings of the 8th Annual ACM-SIAM symposium on discrete algorithms, pp 131–138

Foul A (2006) A \(1\)-center problem on the plane with uniformly distributed demand points. Oper Res Lett 34(3):264–268MathSciNetCrossRefMATH

Frederickson G (1991) Parametric search and locating supply centers in trees. In: Proceedings of the 2nd international workshop on algorithms and data structures (WADS), pp 299–319

Huang L, Li J (2017) Stochastic \(k\)-center and \(j\)-flat-center problems. In: Proceedings of the 28th ACM-SIAM symposium on discrete algorithms (SODA), pp 110–129

Jaromczyk J, Kowaluk M (1994) An efficient algorithm for the Euclidean two-center problem. In: Proceedings of the 10th annual symposium on computational geometry (SoCG), pp 303–311

Keikha V, Aghamolaei S, Mohades A, Ghodsi M (2021) Clustering geometrically-modeled points in the aggregated uncertainty model. CoRR arXiv:2111.13989

Megiddo N (1983) Applying parallel computation algorithms in the design of serial algorithms. J ACM 30(4):852–865MathSciNetCrossRefMATH

Megiddo N, Supowit K (1984) On the complexity of some common geometric location problems. SIAM J Comput 13:182–196MathSciNetCrossRefMATH

Megiddo N, Tamir A, Zemel E, Chandrasekaran R (1981) An \(o(n \log ^2 n)\) algorithm for the \(k\)-th longest path in a tree with applications to location problems. SIAM J Comput 10:328–337MathSciNetCrossRefMATH

Nguyen Q, Zhang J (2021) Line-constrained \(l_\infty \) one-center problem on uncertain points. In: Proceedings of the 3rd international conference on advanced information science and system, vol 71, pp 1–5

Sharir M (1997) A near-linear algorithm for the planar 2-center problem. Discrete Comput Geom 18:125–134MathSciNetCrossRefMATH

Snoeyink J (2007) Maximum independent set for intervals by divide and conquer with pruning. Networks 49:158–159MathSciNetCrossRefMATH

Wang H (2014) Minmax regret 1-facility location on uncertain path networks. Eur J Oper Res 239:636–643MathSciNetCrossRefMATH

Wang H (2020) On the planar two-center problem and circular hulls. In: Proceedings of the 36th international symposium on computational geometry (SoCG), vol 164, pp 68:1–68:14

Wang H, Zhang J (2015) One-dimensional \(k\)-center on uncertain data. Theor Comput Sci 602:114–124MathSciNetCrossRefMATH

Wang H, Zhang J (2016) A note on computing the center of uncertain data on the real line. Oper Res Lett 44:370–373MathSciNetCrossRefMATH

Wang H, Zhang J (2017) Computing the center of uncertain points on tree networks. Algorithmica 78(1):232–254MathSciNetCrossRefMATH

Wang H, Zhang J (2021) An \(o(n\log n)\)-time algorithm for the \(k\)-center problem in trees. SIAM J Comput (SICOMP) 50(2):602–635CrossRefMATH

Title: The two-center problem of uncertain points on a real line
Authors: Haitao Xu
Jingru Zhang
Publication date: 01-03-2023
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2023
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-023-00996-w

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2023

Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

An equilibrium analysis of the impact of real estate price volatility on macroeconomics based on ant colony algorithm

Analysis of modern circulation industry development level using industrial structure mechanism

On optimal due date assignment without restriction and resource allocation in group technology scheduling

Sharp spectral bounds for the vertex-connectivity of regular graphs

AHI: a hybrid machine learning model for complex industrial information systems

Premium Partner