{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T06:52:37Z","timestamp":1775890357269,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"vor","delay-in-days":13,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007511","name":"Universidad Rey Juan Carlos","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007511","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The selection of individuals with similar characteristics from a given population have always been a matter of interest in several scientific areas: data privacy, genetics, art, among others. This work is focused on the maximum intersection of <jats:italic>k<\/jats:italic>-subsets problem (<jats:italic>k<\/jats:italic>MIS). This problem tries to find a subset of <jats:italic>k<\/jats:italic> individuals with the maximum number of features in common from a given population and a set of relevant features. The research presents a Greedy Randomized Adaptive Search Procedure (GRASP) where the local improvement is replaced by a complete Tabu Search metaheuristic with the aim of further improving the quality of the obtained solutions. Additionally, a novel representation of the solution is considered to reduce the computational effort. The experimental comparison carefully analyzes the contribution of each part of the algorithm to the final results as well as performs a thorough comparison with the state-of-the-art method. Results, supported by non-parametric statistical tests, confirms the superiority of the proposal.<\/jats:p>","DOI":"10.1007\/s10732-022-09490-8","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T03:02:37Z","timestamp":1644807757000},"page":"121-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem"],"prefix":"10.1007","volume":"28","author":[{"given":"Alejandra","family":"Casado","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Sergio","family":"P\u00e9rez-Pel\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Jes\u00fas","family":"S\u00e1nchez-Oro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4532-3124","authenticated-orcid":false,"given":"Abraham","family":"Duarte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,14]]},"reference":[{"key":"9490_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.dam.2011.09.019","volume":"164","author":"V Acu\u00f1a","year":"2014","unstructured":"Acu\u00f1a, V., Ferreira, C.E., Freire, A.S., Moreno, E.: Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discrete Appl. Math. 164, 2\u201312 (2014)","journal-title":"Discrete Appl. Math."},{"key":"9490_CR2","doi-asserted-by":"crossref","unstructured":"Bogue, E.T., de Souza, C.C., Xavier, E.C., Freire, A.S.: An integer programming formulation for the maximum k-subset intersection problem. In: Fouilhoux, P., Gouveia, L.E.N., Mahjoub, A.R., Paschos, V.T. (eds.) Combinatorial Optimization, pp. 87\u201399. Springer International Publishing, Cham (2014)","DOI":"10.1007\/978-3-319-09174-7_8"},{"issue":"11","key":"9490_CR3","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.3390\/electronics10111232","volume":"10","author":"P Casas-Mart\u00ednez","year":"2021","unstructured":"Casas-Mart\u00ednez, P., Casado-Ceballos, A., S\u00e1nchez-Oro, J., Pardo, E.G.: Multi-objective grasp for maximizing diversity. Electronics 10(11), 1232 (2021)","journal-title":"Electronics"},{"issue":"6","key":"9490_CR4","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1007\/s10732-020-09452-y","volume":"26","author":"FC Dias","year":"2020","unstructured":"Dias, F.C., Tavares, W.A., de Freitas Costa, J.R.: Reactive VNS algorithm for the maximum k-subset intersection problem. J. Heuristics 26(6), 913\u2013941 (2020)","journal-title":"J. Heuristics"},{"key":"9490_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.ins.2014.10.010","volume":"296","author":"A Duarte","year":"2015","unstructured":"Duarte, A., S\u00e1nchez-Oro, J., Resende, M., Glover, F., Mart\u00ed, R.: Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization. Inf. Sci. 296, 46\u201360 (2015)","journal-title":"Inf. Sci."},{"issue":"2","key":"9490_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"TA Feo","year":"1989","unstructured":"Feo, T.A., Resende, M.G.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2), 67\u201371 (1989)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"9490_CR7","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1287\/opre.42.5.860","volume":"42","author":"TA Feo","year":"1994","unstructured":"Feo, T.A., Resende, M.G., Smith, S.H.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42(5), 860\u2013878 (1994)","journal-title":"Oper. Res."},{"issue":"3","key":"9490_CR8","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BF00383449","volume":"8","author":"B Ganter","year":"1991","unstructured":"Ganter, B., Reuter, K.: Finding all closed sets: a general approach. Order 8(3), 283\u2013290 (1991)","journal-title":"Order"},{"key":"9490_CR9","doi-asserted-by":"crossref","unstructured":"Gao, Y., Gao, X., Li, X., Yao, B., Chen, G.: An embedded GRASP-VNS based two-layer framework for tour recommendation. IEEE Trans. Serv. Comput. (2019)","DOI":"10.1109\/TSC.2019.2963026"},{"key":"9490_CR10","doi-asserted-by":"crossref","unstructured":"Glover, F., Laguna, M.: Tabu search. In: Handbook of combinatorial optimization, pp. 2093\u20132229. Springer (1998)","DOI":"10.1007\/978-1-4613-0303-9_33"},{"key":"9490_CR11","unstructured":"Glover, F.W., Kochenberger, G.A.: Handbook of metaheuristics, vol.\u00a057. Springer Science & Business Media (2006)"},{"issue":"4","key":"9490_CR12","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1007\/s10878-015-9862-1","volume":"31","author":"L Komosko","year":"2016","unstructured":"Komosko, L., Batsyn, M., San Segundo, P., Pardalos, P.M.: A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations. J. Comb. Optim. 31(4), 1665\u20131677 (2016)","journal-title":"J. Comb. Optim."},{"key":"9490_CR13","doi-asserted-by":"publisher","first-page":"104922","DOI":"10.1016\/j.cor.2020.104922","volume":"119","author":"M Li","year":"2020","unstructured":"Li, M., Hao, J.K., Wu, Q.: General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem. Comput. Oper. Res. 119, 104922 (2020)","journal-title":"Comput. Oper. Res."},{"key":"9490_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cor.2017.10.011","volume":"91","author":"R Mart\u00ed","year":"2018","unstructured":"Mart\u00ed, R., Mart\u00ednez-Gavara, A., S\u00e1nchez-Oro, J., Duarte, A.: Tabu search for the dynamic bipartite drawing problem. Comput. Oper. Res. 91, 1\u201312 (2018)","journal-title":"Comput. Oper. Res."},{"issue":"11","key":"9490_CR15","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097\u20131100 (1997)","journal-title":"Comput. Oper. Res."},{"key":"9490_CR16","doi-asserted-by":"crossref","unstructured":"Nussbaum, D., Pu, S., Sack, J.R., Uno, T., Zarrabi-Zadeh, H.: Finding maximum edge bicliques in convex bipartite graphs. In: International Computing and Combinatorics Conference, pp. 140\u2013149. Springer (2010)","DOI":"10.1007\/978-3-642-14031-0_17"},{"key":"9490_CR17","doi-asserted-by":"crossref","unstructured":"Pandey, A., Sharma, G., Jain, N.: Maximum weighted edge biclique problem on bipartite graphs. In: Conference on Algorithms and Discrete Applied Mathematics, pp. 116\u2013128. Springer (2020)","DOI":"10.1007\/978-3-030-39219-2_10"},{"issue":"3","key":"9490_CR18","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131(3), 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"9490_CR19","doi-asserted-by":"publisher","first-page":"e12540","DOI":"10.1111\/exsy.12540","volume":"37","author":"S P\u00e9rez-Pel\u00f3","year":"2020","unstructured":"P\u00e9rez-Pel\u00f3, S., S\u00e1nchez-Oro, J., Duarte, A.: Finding weaknesses in networks using greedy randomized adaptive search procedure and path relinking. Expert Syst. 37(6), e12540 (2020)","journal-title":"Expert Syst."},{"key":"9490_CR20","doi-asserted-by":"crossref","unstructured":"Saad, A., Kafafy, A., Abd-El-Raof, O., El-Hefnawy, N.: A grasp-genetic metaheuristic applied on multi-processor task scheduling systems. In: 2018 13th International Conference on Computer Engineering and Systems (ICCES), pp. 109\u2013115. IEEE (2018)","DOI":"10.1109\/ICCES.2018.8639377"},{"key":"9490_CR21","doi-asserted-by":"crossref","unstructured":"San\u00a0Segundo, P., Gal\u00e1n, R., Mat\u00eda, F., Rodr\u00edguez-Losada, D., Jim\u00e9nez, A.: Efficient search using bitboard models. In: 2006 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI\u201906), pp. 132\u2013138. IEEE (2006)","DOI":"10.1109\/ICTAI.2006.53"},{"key":"9490_CR22","unstructured":"Vinterbo, S.A.: A note on the hardness of the k-ambiguity problem. Tech. Rep. DSG-TR-2002-006, Decision Systems Group\/Harvard Medical School, 75 Francis Street, Boston, MA 02115, USA (2002)"},{"key":"9490_CR23","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/j.ins.2017.12.012","volume":"432","author":"Y Wang","year":"2018","unstructured":"Wang, Y., Cai, S., Yin, M.: New heuristic approaches for maximum balanced biclique problem. Inf. Sci. 432, 362\u2013375 (2018)","journal-title":"Inf. Sci."},{"issue":"12","key":"9490_CR24","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.ipl.2012.03.007","volume":"112","author":"EC Xavier","year":"2012","unstructured":"Xavier, E.C.: A note on a maximum k-subset intersection problem. Inf. Process. Lett. 112(12), 471\u2013472 (2012)","journal-title":"Inf. Process. Lett."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-022-09490-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-022-09490-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-022-09490-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T09:04:02Z","timestamp":1645434242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-022-09490-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["9490"],"URL":"https:\/\/doi.org\/10.1007\/s10732-022-09490-8","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2]]},"assertion":[{"value":"17 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}