{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:39:42Z","timestamp":1763545182489,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T00:00:00Z","timestamp":1678924800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T00:00:00Z","timestamp":1678924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007657","name":"University of Ljubljana","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007657","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of computing the <jats:italic>distance-based representative skyline<\/jats:italic> in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Mathematics; Optimization and Learning - Third International Conference, OLA 2020] in the context of multi-objective optimization. Given a set <jats:italic>P<\/jats:italic> of <jats:italic>n<\/jats:italic> points in the plane and a parameter <jats:italic>k<\/jats:italic>, the task is to select <jats:italic>k<\/jats:italic> points of the skyline defined by <jats:italic>P<\/jats:italic> (also known as Pareto front for <jats:italic>P<\/jats:italic>) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\log h)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>h<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where <jats:italic>h<\/jats:italic> is the number of points in the skyline of <jats:italic>P<\/jats:italic>. We also show that the decision problem can be solved in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\log k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time and the optimization problem can be solved in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n \\log k + n {{\\,\\textrm{loglog}\\,}}n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>loglog<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. This improves previous algorithms and is optimal for a large range of values of <jats:italic>k<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s10898-023-01280-1","type":"journal-article","created":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T03:03:51Z","timestamp":1678935831000},"page":"441-466","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Faster distance-based representative skyline and k-center along pareto front in the plane"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3183-4126","authenticated-orcid":false,"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,16]]},"reference":[{"issue":"3","key":"1280_CR1","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1016\/j.ejor.2006.08.008","volume":"181","author":"N Beume","year":"2007","unstructured":"Beume, N., Naujoks, B., Emmerich, M.T.M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653\u20131669 (2007). https:\/\/doi.org\/10.1016\/j.ejor.2006.08.008","journal-title":"Eur. J. Oper. Res."},{"key":"1280_CR2","doi-asserted-by":"publisher","unstructured":"B\u00f6rzs\u00f6nyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proc. 17th International Conference on Data Engineering, ICDE 2001, pages 421\u2013430. IEEE Computer Society, (2001). https:\/\/doi.org\/10.1109\/ICDE.2001.914855","DOI":"10.1109\/ICDE.2001.914855"},{"key":"1280_CR3","doi-asserted-by":"publisher","unstructured":"\u00c7al\u0131, H., Labb\u00e9, M., Yaman, H.: $$p$$-center problems. In:Gilbert Laporte, Stefan Nickel, and Francisco Saldanha da Gama, editors, Location Science, chapter\u00a03, pages 51\u201365. Springer, 2nd edition, (2019). https:\/\/doi.org\/10.1007\/978-3-030-32177-2_3","DOI":"10.1007\/978-3-030-32177-2_3"},{"issue":"4","key":"1280_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discret. Comput. Geom. 16(4), 361\u2013368 (1996). https:\/\/doi.org\/10.1007\/BF02712873","journal-title":"Discret. Comput. Geom."},{"key":"1280_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00863-2","author":"J Choi","year":"2019","unstructured":"Choi, J., Cabello, S., Ahn, H.-K.: Maximizing dominance in the plane and its applications Algorithmica, to appear. Preliminary Vers. in WADS (2019). https:\/\/doi.org\/10.1007\/s00453-021-00863-2","journal-title":"Preliminary Vers. in WADS"},{"key":"1280_CR6","unstructured":"Dasgupta, S., Papadimitriou, C.\u00a0H., Vazirani, U.\u00a0V.: Algorithms. McGraw-Hill, (2008)"},{"key":"1280_CR7","doi-asserted-by":"publisher","unstructured":"Dupin, N., Nielsen, F., Talbi, El-G., Unified polynomial dynamic programming algorithms for p-center variants in a 2d Pareto front. Mathematics, 9(4),: Preliminary version in Optimization and Learning - Third International Conference. OLA 2020,(2021). https:\/\/doi.org\/10.3390\/math9040453","DOI":"10.3390\/math9040453"},{"issue":"3","key":"1280_CR8","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/s11047-018-9685-y","volume":"17","author":"MTM Emmerich","year":"2018","unstructured":"Emmerich, M.T.M., Deutz, A.H.: A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Nat. Comput. 17(3), 585\u2013609 (2018). https:\/\/doi.org\/10.1007\/s11047-018-9685-y","journal-title":"Nat. Comput."},{"key":"1280_CR9","unstructured":"Frederickson, G.N.: Optimal algorithms for tree partitioning. In: Proc. 2nd Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, SODA 1991, pages 168\u2013177. ACM\/SIAM, (1991). URL: http:\/\/dl.acm.org\/citation.cfm?id=127787.127822"},{"key":"1280_CR10","doi-asserted-by":"publisher","unstructured":"Frederickson, G.N.: Parametric search and locating supply centers in trees. In: Algorithms and Data Structures, 2nd Workshop WADS 1991, volume 519 of Lecture Notes in Computer Science, pages 299\u2013319. Springer, (1991). https:\/\/doi.org\/10.1007\/BFb0028271","DOI":"10.1007\/BFb0028271"},{"issue":"2","key":"1280_CR11","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"GN Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in X+Y and matrices with sorted columns. J. Comput. Syst. Sci. 24(2), 197\u2013208 (1982). https:\/\/doi.org\/10.1016\/0022-0000(82)90048-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1280_CR12","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"GN Frederickson","year":"1984","unstructured":"Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: Sorted matrices. SIAM J. Comput. 13(1), 14\u201330 (1984). https:\/\/doi.org\/10.1137\/0213002","journal-title":"SIAM J. Comput."},{"key":"1280_CR13","unstructured":"Frederickson, G.N., Zhou, S.: Optimal parametric search for path and tree partitioning. CoRR, abs\/1711.00599, (2017). arXiv:1711.00599"},{"key":"1280_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90224-5","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1280_CR15","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985). https:\/\/doi.org\/10.1287\/moor.10.2.180","journal-title":"Math. Oper. Res."},{"key":"1280_CR16","doi-asserted-by":"publisher","unstructured":"Kaplan, H., Kozma, L., Zamir, O., Zwick, U.: Selection from heaps, row-sorted matrices, and X+Y using soft heaps. In: 2nd Symposium on Simplicity in Algorithms, SOSA@SODA,: volume 69 of OASICS, pages 5:1\u20135:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 2019,(2019). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.5","DOI":"10.4230\/OASIcs.SOSA.2019.5"},{"key":"1280_CR17","doi-asserted-by":"publisher","unstructured":"Kirkpatrick, D.G., Seidel, R.: Output-size sensitive algorithms for finding maximal vectors. In: Joseph O\u2019Rourke, editor, Proc. 1st Annual Symposium on Computational Geometry, SoCG 1985, pages 89\u201396. ACM, (1985). https:\/\/doi.org\/10.1145\/323233.323246","DOI":"10.1145\/323233.323246"},{"issue":"4","key":"1280_CR18","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"HT Kung","year":"1975","unstructured":"Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469\u2013476 (1975). https:\/\/doi.org\/10.1145\/321906.321910","journal-title":"J. ACM"},{"issue":"2","key":"1280_CR19","doi-asserted-by":"publisher","first-page":"26:1","DOI":"10.1145\/3300148","volume":"52","author":"M Li","year":"2019","unstructured":"Li, M., Yao, X.: Quality evaluation of solution sets in multiobjective optimisation: A survey. ACM Comput. Surv. 52(2), 26:1-26:38 (2019). https:\/\/doi.org\/10.1145\/3300148","journal-title":"ACM Comput. Surv."},{"key":"1280_CR20","doi-asserted-by":"publisher","unstructured":"Lin, X., Yuan, Y., Zhang, Q., Zhang, Y.: Selecting stars: The k most representative skyline operator. In: Proc. 23rd International Conference on Data Engineering, ICDE 2007, pages 86\u201395. IEEE Computer Society, (2007). https:\/\/doi.org\/10.1109\/ICDE.2007.367854","DOI":"10.1109\/ICDE.2007.367854"},{"issue":"4","key":"1280_CR21","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/s11280-016-0406-0","volume":"20","author":"R Mao","year":"2017","unstructured":"Mao, R., Cai, T., Li, R.-H., Yu, J.X., Li, J.: Efficient distance-based representative skyline computation in 2D space. World Wide Web 20(4), 621\u2013638 (2017). https:\/\/doi.org\/10.1007\/s11280-016-0406-0","journal-title":"World Wide Web"},{"issue":"4","key":"1280_CR22","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N Megiddo","year":"1979","unstructured":"Megiddo, N.: Combinatorial optimization with rational objective functions. Math. Oper. Res. 4(4), 414\u2013424 (1979). https:\/\/doi.org\/10.1287\/moor.4.4.414","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1280_CR23","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TEVC.2013.2290086","volume":"18","author":"A Mukhopadhyay","year":"2014","unstructured":"Mukhopadhyay, A., Maulik, U., Bandyopadhyay, S., Coello, C.A.C.: A survey of multiobjective evolutionary algorithms for data mining: Part I. IEEE Trans. Evol. Comput. 18(1), 4\u201319 (2014). https:\/\/doi.org\/10.1109\/TEVC.2013.2290086","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"5","key":"1280_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0020-0190(96)00116-0","volume":"59","author":"F Nielsen","year":"1996","unstructured":"Nielsen, F.: Output-sensitive peeling of convex and maximal layers. Inf. Process. Lett. 59(5), 255\u2013259 (1996). https:\/\/doi.org\/10.1016\/0020-0190(96)00116-0","journal-title":"Inf. Process. Lett."},{"key":"1280_CR25","doi-asserted-by":"publisher","unstructured":"Peng, Raymond C-W., Wong, P.: Skyline queries and pareto optimality. In: M.\u00a0Tamer Liu, Lingand\u00a0\u00d6zsu, editor, Encyclopedia of Database Systems, pages 1\u20134. Springer New York, New York, NY, (2016). https:\/\/doi.org\/10.1007\/978-1-4899-7993-3_80684-1","DOI":"10.1007\/978-1-4899-7993-3_80684-1"},{"issue":"3","key":"1280_CR26","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/2000824.2000829","volume":"36","author":"K Stefanidis","year":"2011","unstructured":"Stefanidis, K., Koutrika, G., Pitoura, E.: A survey on representation, composition and application of preferences in database systems. ACM Trans. Database Syst. 36(3), 19:1-19:45 (2011). https:\/\/doi.org\/10.1145\/2000824.2000829","journal-title":"ACM Trans. Database Syst."},{"key":"1280_CR27","doi-asserted-by":"publisher","unstructured":"Tao, Y., Ding, L., Lin, X, Pei, J.: Distance-based representative skyline. In: Proc. 25th International Conference on Data Engineering, ICDE 2009, pages 892\u2013903. IEEE Computer Society, (2009). https:\/\/doi.org\/10.1109\/ICDE.2009.84","DOI":"10.1109\/ICDE.2009.84"},{"key":"1280_CR28","unstructured":"Tao, Y., Li, J., Ding, L., Lin, X., Pei, J.: On representing skylines by distance, (2013). Long version of [27] available at https:\/\/www.cse.cuhk.edu.hk\/~taoyf\/paper\/icde09-long.pdf via https:\/\/www.cse.cuhk.edu.hk\/~taoyf\/pub.html"},{"issue":"2\u20133","key":"1280_CR29","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.comgeo.2004.03.006","volume":"28","author":"R van Oostrum","year":"2004","unstructured":"van Oostrum, R., Veltkamp, R.C.: Parametric search made practical. Comput. Geom. 28(2\u20133), 75\u201388 (2004). https:\/\/doi.org\/10.1016\/j.comgeo.2004.03.006","journal-title":"Comput. Geom."},{"key":"1280_CR30","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, (2011). http:\/\/www.cambridge.org\/de\/knowledge\/isbn\/item5759340\/?site_locale=de_DE","DOI":"10.1017\/CBO9780511921735"},{"key":"1280_CR31","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.eswa.2018.11.004","volume":"119","author":"B Yin","year":"2019","unstructured":"Yin, B., Wei, X., Liu, Y.: Finding the informative and concise set through approximate skyline queries. Expert Syst. Appl. 119, 289\u2013310 (2019). https:\/\/doi.org\/10.1016\/j.eswa.2018.11.004","journal-title":"Expert Syst. Appl."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01280-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-023-01280-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01280-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T04:05:14Z","timestamp":1692417914000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-023-01280-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,16]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1280"],"URL":"https:\/\/doi.org\/10.1007\/s10898-023-01280-1","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2023,3,16]]},"assertion":[{"value":"25 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}