IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v320y2023i1d10.1007_s10479-022-04764-7.html
   My bibliography  Save this article

Maximizing single attribute diversity in group selection

Author

Listed:
  • Sergey Kovalev

    (25 rue de l’Université)

  • Isabelle Chalamon

    (25 rue de l’Université)

  • Fabio J. Petani

    (25 rue de l’Université)

Abstract

The studied problem consists in selecting a group of k entities out of n entities such that their diversity is maximized. Each entity is assumed to be characterized by a single numerical attribute. The diversity is measured by the total pairwise Euclidean or squared Euclidean distance. The problem appears in the formation of social or working groups. Under certain conditions, diversity is perceived as a positive factor influencing the group’s effectiveness. We propose simple $$O(n+k\log k)$$ O ( n + k log k ) time algorithms to solve this problem for both the total Euclidean and squared Euclidean distances.

Suggested Citation

  • Sergey Kovalev & Isabelle Chalamon & Fabio J. Petani, 2023. "Maximizing single attribute diversity in group selection," Annals of Operations Research, Springer, vol. 320(1), pages 535-540, January.
    • Handle: RePEc:spr:annopr:v:320:y:2023:i:1:d:10.1007_s10479-022-04764-7
    DOI: 10.1007/s10479-022-04764-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-022-04764-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-022-04764-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lei, Ting L. & Church, Richard L., 2015. "On the unified dispersion problem: Efficient formulations and exact algorithms," European Journal of Operational Research, Elsevier, vol. 241(3), pages 622-630.
    2. Pankaj Dutta & Aayush Jain & Asish Gupta, 2020. "Performance analysis of non-banking finance companies using two-stage data envelopment analysis," Annals of Operations Research, Springer, vol. 295(1), pages 91-116, December.
    3. Amirgaliyeva, Zhazira & Mladenović, Nenad & Todosijević, Raca & Urošević, Dragan, 2017. "Solving the maximum min-sum dispersion by alternating formulations of two different problems," European Journal of Operational Research, Elsevier, vol. 260(2), pages 444-459.
    4. Martí, Rafael & Gallego, Micael & Duarte, Abraham, 2010. "A branch and bound algorithm for the maximum diversity problem," European Journal of Operational Research, Elsevier, vol. 200(1), pages 36-44, January.
    5. S. S. Ravi & D. J. Rosenkrantz & G. K. Tayi, 1994. "Heuristic and Special Case Algorithms for Dispersion Problems," Operations Research, INFORMS, vol. 42(2), pages 299-310, April.
    6. Şenay Yaşar Sağlam & W. Nick Street, 2018. "Distant diversity in dynamic class prediction," Annals of Operations Research, Springer, vol. 263(1), pages 5-19, April.
    7. Lijo John & Anand Gurumurthy & Gunjan Soni & Vipul Jain, 2019. "Modelling the inter-relationship between factors affecting coordination in a humanitarian supply chain: a case of Chennai flood relief," Annals of Operations Research, Springer, vol. 283(1), pages 1227-1258, December.
    8. Mahdi Moeini & Oliver Wendt, 2018. "A Heuristic for Solving the Maximum Dispersion Problem," Operations Research Proceedings, in: Andreas Fink & Armin Fügenschuh & Martin Josef Geiger (ed.), Operations Research Proceedings 2016, pages 405-410, Springer.
    9. Aringhieri, Roberto & Cordone, Roberto & Grosso, Andrea, 2015. "Construction and improvement algorithms for dispersion problems," European Journal of Operational Research, Elsevier, vol. 242(1), pages 21-33.
    10. Anatoly B. Schmidt, 2019. "Managing portfolio diversity within the mean variance theory," Annals of Operations Research, Springer, vol. 282(1), pages 315-329, November.
    11. Ríos-Mercado, Roger Z. & Bard, Jonathan F., 2019. "An exact algorithm for designing optimal districts in the collection of waste electric and electronic equipment through an improved reformulation," European Journal of Operational Research, Elsevier, vol. 276(1), pages 259-271.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    2. Parreño, Francisco & Álvarez-Valdés, Ramón & Martí, Rafael, 2021. "Measuring diversity. A review and an empirical analysis," European Journal of Operational Research, Elsevier, vol. 289(2), pages 515-532.
    3. Arne Schulz, 2022. "A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values," Annals of Operations Research, Springer, vol. 318(1), pages 501-530, November.
    4. Schulz, Arne, 2021. "The balanced maximally diverse grouping problem with block constraints," European Journal of Operational Research, Elsevier, vol. 294(1), pages 42-53.
    5. Wu, Qinghua & Hao, Jin-Kao, 2013. "A hybrid metaheuristic method for the Maximum Diversity Problem," European Journal of Operational Research, Elsevier, vol. 231(2), pages 452-464.
    6. Anna Martínez-Gavara & Vicente Campos & Manuel Laguna & Rafael Martí, 2017. "Heuristic solution approaches for the maximum minsum dispersion problem," Journal of Global Optimization, Springer, vol. 67(3), pages 671-686, March.
    7. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    8. Gliesch, Alex & Ritt, Marcus, 2021. "A hybrid heuristic for the maximum dispersion problem," European Journal of Operational Research, Elsevier, vol. 288(3), pages 721-735.
    9. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.
    10. Rennen, G., 2008. "Subset Selection from Large Datasets for Kriging Modeling," Discussion Paper 2008-26, Tilburg University, Center for Economic Research.
    11. Shi, Jianmai & Chen, Wenyi & Verter, Vedat, 2023. "The joint impact of environmental awareness and system infrastructure on e-waste collection," European Journal of Operational Research, Elsevier, vol. 310(2), pages 760-772.
    12. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    13. Chiang Kao & Shiang-Tai Liu, 2022. "Stochastic efficiencies of network production systems with correlated stochastic data: the case of Taiwanese commercial banks," Annals of Operations Research, Springer, vol. 315(2), pages 1151-1174, August.
    14. Fan Chen & Sen Liu & Andrea Appolloni, 2020. "Horizontal Coordination of I-LNGOs in the Humanitarian Supply Chain: An Evolutionary Game Approach," Sustainability, MDPI, vol. 12(15), pages 1-21, July.
    15. Erkut, E. & ReVelle, C. & Ulkusal, Y., 1996. "Integer-friendly formulations for the r-separation problem," European Journal of Operational Research, Elsevier, vol. 92(2), pages 342-351, July.
    16. Nicolas Dupin & Frank Nielsen & El-Ghazali Talbi, 2021. "Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front," Mathematics, MDPI, vol. 9(4), pages 1-30, February.
    17. Alessandro Hill & Eduardo Lalla-Ruiz & Stefan Voß & Marcos Goycoolea, 2019. "A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem," Journal of Scheduling, Springer, vol. 22(2), pages 173-182, April.
    18. Balabhaskar Balasundaram & Sergiy Butenko & Illya V. Hicks, 2011. "Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem," Operations Research, INFORMS, vol. 59(1), pages 133-142, February.
    19. Syed Kumail Abbas Rizvi & Bushra Naqvi & Nawazish Mirza, 2022. "Is green investment different from grey? Return and volatility spillovers between green and grey energy ETFs," Annals of Operations Research, Springer, vol. 313(1), pages 495-524, June.
    20. Lei, Ting L. & Church, Richard L., 2015. "On the unified dispersion problem: Efficient formulations and exact algorithms," European Journal of Operational Research, Elsevier, vol. 241(3), pages 622-630.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:320:y:2023:i:1:d:10.1007_s10479-022-04764-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.