Cited By
View all- Acharyya AKeikha VSaumell MSilveira R(2024)Computing Largest Minimum Color-Spanning Intervals of Imprecise PointsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_6(81-96)Online publication date: 18-Mar-2024
Computing k-centers of uncertain points on a real line
Authors: 
Ran Hu, Jingru ZhangAuthors Info & Claims
References
[1]
S. Alipour, A. Jafari, Improvements on the k-center problem for uncertain data, in: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018, pp. 425–433.
[2]
I. Averbakh, V. Lebedev, Interval data minmax regret network optimization problems, Discrete Appl. Math. 138 (3) (2004) 289–301.
[3]
M.A. Bender, M. Farach-Colton, The lca problem revisited, in: Proceeding of the 4th Latin American Symposium on Theoretical Informatics, 2000, pp. 88–94.
[4]
D.Z. Chen, J. Li, H. Wang, Efficient algorithms for one-dimensional k-center problems, Theor. Comput. Sci. 592 (2015) 135–142.
[5]
D.Z. Chen, H. Wang, A note on searching line arrangements and applications, Inf. Process. Lett. 113 (2013) 518–521.
[6]
H. Fournier, A. Vigneron, Fitting a step function to a point set, Algorithmica 60 (1) (2011) 95–109.
[7]
G. Frederickson, Optimal algorithms for tree partitioning, in: The 2nd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA), 1991, pp. 168–177.
[8]
G. Frederickson, Parametric search and locating supply centers in trees, in: The 2nd International Workshop on Algorithms and Data Structures, 1991, pp. 299–319.
[9]
U. Gupta, D. Lee, J. Leung, Efficient algorithms for interval graphs and circular-arc graphs, Networks 12 (4) (1982) 459–467.
[10]
D. Harel, R.E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM J. Comput. 13 (2) (1984) 338–355.
[11]
L. Huang, J. Li, Stochastic k-center and j-flat-center problems, in: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, pp. 110–129.
[12]
S. Jadhav, A. Mukhopadhyay, B. Bhattacharya, An optimal algorithm for the intersection radius of a set of convex polygons, J. Algorithms 20 (2) (1996) 244–267.
[13]
Keikha, V.; Aghamolaei, S.; Mohades, A.; Ghodsi, M. (2021): Clustering geometrically-modeled points in the aggregated uncertainty model. CoRR arXiv:2111.13989.
[14]
B. Khelifa, H. Haffaf, M. Madjid, D. Llewellyn-Jones, Monitoring connectivity in wireless sensor networks, in: 2009 IEEE Symposium on Computers and Communications, 2009, pp. 507–512.
[15]
M. Löffler, M.V. Kreveld, Largest bounding box, smallest diameter, and related problems on imprecise points, Comput. Geom. 43 (4) (2010) 419–433.
[16]
N. Megiddo, K.J. Supowit, On the complexity of some common geometric location problems, SIAM J. Comput. 13 (1984) 182–196.
[17]
H. Wang, J. Zhang, One-dimensional k-center on uncertain data, Theor. Comput. Sci. 602 (2015) 114–124.
[18]
H. Wang, J. Zhang, Computing the rectilinear center of uncertain points in the plane, Int. J. Comput. Geom. Appl. 28 (2018) 271–288.
[19]
H. Wang, J. Zhang, Covering uncertain points in a tree, Algorithmica 81 (2019) 2346–2376.
Index Terms
- Computing k-centers of uncertain points on a real line
Index terms have been assigned to the content through auto-classification.
Recommendations
Line-Constrained L∞ One-Center Problem on Uncertain Points
AISS '21: Proceedings of the 3rd International Conference on Advanced Information Science and SystemProblems on uncertain data have attracted significant attention due to the imprecise nature of the measurement. In this paper, we consider the (weighted) L∞ one-center problem on uncertain data with an addition constraint that requires the sought ...
Covering Uncertain Points in a Tree
In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set $${\mathcal {P}}$$P of n (weighted) demand points, and the location of each demand point $$P_i\in {{\mathcal {P}}}$$Pi?P is uncertain but is ...
The two-center problem of uncertain points on a real line
AbstractFacility 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 of n uncertain points on the line. Each ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 May 2022
Author Tags
Qualifiers
- Rapid-communication
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View all- Acharyya AKeikha VSaumell MSilveira R(2024)Computing Largest Minimum Color-Spanning Intervals of Imprecise PointsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_6(81-96)Online publication date: 18-Mar-2024
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in