{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:57:02Z","timestamp":1725796622532},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_10","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T10:04:30Z","timestamp":1404554670000},"page":"104-115","source":"Crossref","is-referenced-by-count":2,"title":["One-Dimensional k-Center on Uncertain Data"],"prefix":"10.1007","author":[{"given":"Haitao","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingru","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Cheng, S.-W., Tao, Y., Yi, K.: Indexing uncertain data. In: Proc. of the 28th Symposium on Principles of Database Systems (PODS), pp. 137\u2013146 (2009)","DOI":"10.1145\/1559795.1559816"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Efrat, A., Sankararaman, S., Zhang, W.: Nearest-neighbor searching under uncertainty. In: Proc. of the 31st Symposium on Principles of Database Systems (PODS), pp. 225\u2013236 (2012)","DOI":"10.1145\/2213556.2213588"},{"issue":"4","key":"10_CR3","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Computing Surveys\u00a030(4), 412\u2013458 (1998)","journal-title":"ACM Computing Surveys"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Aggarwal, C., Yu, P.S.: A framework for clustering uncertain data streams. In: Proc. of the 24th International Conference on Data Engineering (ICDE), pp. 150\u2013159 (2008)","DOI":"10.1109\/ICDE.2008.4497423"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM Journal on Computing\u00a033, 544\u2013562 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.disopt.2004.12.001","volume":"2","author":"I. Averbakh","year":"2005","unstructured":"Averbakh, I., Bereg, S.: Facility location problems with uncertainty on the plane. Discrete Optimization\u00a02, 3\u201334 (2005)","journal-title":"Discrete Optimization"},{"key":"10_CR7","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0966-8349(98)00033-3","volume":"5","author":"I. Averbakh","year":"1997","unstructured":"Averbakh, I., Berman, O.: Minimax regret p-center location on a network with demand uncertainty. Location Science\u00a05, 247\u2013254 (1997)","journal-title":"Location Science"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Badoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. of the 34th Annual Symposium on Theory of Computing (STOC), pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0925-7721(97)00025-4","volume":"10","author":"H. Br\u00f6nnimann","year":"1998","unstructured":"Br\u00f6nnimann, H., Chazelle, B.: Optimal slope selection via cuttings. Computational Geometry: Theory and Applications\u00a010(1), 23\u201329 (1998)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"1","key":"10_CR10","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/BF01581045","volume":"22","author":"R. Chandrasekaran","year":"1982","unstructured":"Chandrasekaran, R., Tamir, A.: Polynomially bounded algorithms for locating p-centers on a tree. Mathematical Programming\u00a022(1), 304\u2013315 (1982)","journal-title":"Mathematical Programming"},{"key":"10_CR11","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/11731139_24","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"M. Chau","year":"2006","unstructured":"Chau, M., Cheng, R., Kao, B., Ng, J.: Uncertain data mining: An example in clustering location data. In: Ng, W.-K., Kitsuregawa, M., Li, J., Chang, K. (eds.) PAKDD 2006. LNCS (LNAI), vol.\u00a03918, pp. 199\u2013204. Springer, Heidelberg (2006)"},{"issue":"1","key":"10_CR12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.: Fractional cascading: I. A data structuring technique. Algorithmica\u00a01(1), 133\u2013162 (1986)","journal-title":"Algorithmica"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1016\/j.ipl.2013.04.011","volume":"113","author":"D.Z. Chen","year":"2013","unstructured":"Chen, D.Z., Wang, H.: A note on searching line arrangements and applications. Information Processing Letters\u00a0113, 518\u2013521 (2013)","journal-title":"Information Processing Letters"},{"key":"10_CR14","unstructured":"Chen, D.Z., Li, J., Wang, H.: Efficient algorithms for one-dimensional k-center problems. arXiv:1301.7512 (2013)"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/978-3-642-25591-5_60","volume-title":"Algorithms and Computation","author":"D.Z. Chen","year":"2011","unstructured":"Chen, D.Z., Wang, H.: Efficient algorithms for the weighted k-center problem on a real line. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 584\u2013593. Springer, Heidelberg (2011)"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Cheng, R., Xia, Y., Prabhakar, S., Shah, R., Vitter, J.S.: Efficient indexing methods for probabilistic threshold queries over uncertain data. In: Proc. of the 30th International Conference on Very Large Data Bases (VLDB), pp. 876\u2013887 (2004)","DOI":"10.1016\/B978-012088469-8\/50077-2"},{"issue":"1","key":"10_CR17","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM\u00a034(1), 200\u2013208 (1987)","journal-title":"Journal of the ACM"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Cormode, G., McGregor, A.: Approximation algorithms for clustering uncertain data. In: Proc. of the 27th Symposium on Principles of Database Systems (PODS), pp. 191\u2013200 (2008)","DOI":"10.1145\/1376916.1376944"},{"key":"10_CR19","volume-title":"Facility Location: Applications and Theory","author":"Z. Drezner","year":"2004","unstructured":"Drezner, Z., Hamacher, H.W.: Facility Location: Applications and Theory. Springer, New York (2004)"},{"key":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/BFb0028271","volume-title":"Algorithms and Data Structures","author":"G.N. Frederickson","year":"1991","unstructured":"Frederickson, G.N.: Parametric search and locating supply centers in trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 299\u2013319. Springer, Heidelberg (1991)"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks\u00a012, 459\u2013467 (1982)","journal-title":"Networks"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D. Hochbaum","year":"1985","unstructured":"Hochbaum, D., Shmoys, D.: A best possible heuristic for the k-center problem. Mathematics of Operations Research\u00a010, 180\u2013184 (1985)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/978-3-642-22300-6_46","volume-title":"Algorithms and Data Structures","author":"P. Kamousi","year":"2011","unstructured":"Kamousi, P., Chan, T.M., Suri, S.: Closest pair and the post office problem for stochastic points. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 548\u2013559. Springer, Heidelberg (2011)"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Kamousi, P., Chan, T.M., Suri, S.: Stochastic minimum spanning trees in Euclidean spaces. In: Proc. of the 27th Annual Symposium on Computational Geometry (SoCG), pp. 65\u201374 (2011)","DOI":"10.1145\/1998196.1998206"},{"issue":"3","key":"10_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(93)90234-Z","volume":"47","author":"M. Katz","year":"1993","unstructured":"Katz, M., Sharir, M.: Optimal slope selection via expanders. Information Processing Letters\u00a047(3), 115\u2013122 (1993)","journal-title":"Information Processing Letters"},{"issue":"4","key":"10_CR26","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM\u00a030(4), 852\u2013865 (1983)","journal-title":"Journal of the ACM"},{"issue":"4","key":"10_CR27","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in R\n                  3 and related problems. SIAM Journal on Computing\u00a012(4), 759\u2013776 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM Journal on Comuting\u00a013, 182\u2013196 (1984)","journal-title":"SIAM Journal on Comuting"},{"issue":"4","key":"10_CR29","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0212051","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N., Tamir, A.: New results on the complexity of p-centre problems. SIAM J. on Computing\u00a012(4), 751\u2013758 (1983)","journal-title":"SIAM J. on Computing"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/0210023","volume":"10","author":"N. Megiddo","year":"1981","unstructured":"Megiddo, N., Tamir, A., Zemel, E., Chandrasekaran, R.: An O(n log2\n                  n) algorithm for the k-th longest path in a tree with applications to location problems. SIAM J. on Computing\u00a010, 328\u2013337 (1981)","journal-title":"SIAM J. on Computing"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Ngai, W.K., Kao, B., Chui, C.K., Cheng, R., Chau, M., Yip, K.Y.: Efficient clustering of uncertain data. In: Proc. of the 6th International Conference on Data Mining (ICDM), pp. 436\u2013445 (2006)","DOI":"10.1109\/ICDM.2006.63"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1002\/net.20150","volume":"49","author":"J. Snoeyink","year":"2007","unstructured":"Snoeyink, J.: Maximum independent set for intervals by divide and conquer with pruning. Networks\u00a049, 158\u2013159 (2007)","journal-title":"Networks"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1080\/074081791009022","volume":"38","author":"L.V. Snyder","year":"2006","unstructured":"Snyder, L.V.: Facility location under uncertainty: A review. IIE Transactions\u00a038, 537\u2013554 (2006)","journal-title":"IIE Transactions"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"Tao, Y., Xiao, X., Cheng, R.: Range search on multidimensional uncertain data. ACM Transactions on Database Systems\u00a032 (2007)","DOI":"10.1145\/1272743.1272745"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.comgeo.2004.03.006","volume":"28","author":"R. Oostrum van","year":"2004","unstructured":"van Oostrum, R., Veltkamp, R.C.: Parametric search made practical. Computational Geometry: Theory and Applications\u00a028, 75\u201388 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Wang, H.: Minmax regret 1-facility location on uncertain path networks. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol.\u00a08283, pp. 733\u2013743. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-45030-3_68"},{"key":"10_CR37","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/TKDE.2008.135","volume":"21","author":"M.L. Yiu","year":"2009","unstructured":"Yiu, M.L., Mamoulis, N., Dai, X., Tao, Y., Vaitis, M.: Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data. IEEE Transactions on Knowledge and Data Engineering\u00a021, 108\u2013122 (2009)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"Yu, H.-I., Lin, T.-C., Wang, B.-F.: Improved algorithms for the minmax-regret 1-center and 1-median problems. ACM Transactions on Algorithms\u00a04(3), Article No. 36 (2008)","DOI":"10.1145\/1367064.1367076"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:33:52Z","timestamp":1558924432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}