IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i2p359-376.html
   My bibliography  Save this article

Group Equality in Adaptive Submodular Maximization

Author

Listed:
  • Shaojie Tang

    (Naveen Jindal School of Management, The University of Texas at Dallas, Richardson, Texas 75080)

  • Jing Yuan

    (Department of Computer Science and Engineering, The University of North Texas, Denton, Texas 76205)

Abstract

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations.

Suggested Citation

  • Shaojie Tang & Jing Yuan, 2024. "Group Equality in Adaptive Submodular Maximization," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 359-376, March.
  • Handle: RePEc:inm:orijoc:v:36:y:2024:i:2:p:359-376
    DOI: 10.1287/ijoc.2022.0384
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0384
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2022.0384?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
    ---><---

    References listed on IDEAS

    as
    1. Shaojie Tang & Jing Yuan, 2023. "Beyond submodularity: a unified framework of randomized set selection with group fairness constraints," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-22, May.
    2. Jing Yuan & Shaojie Tang, 2023. "Group fairness in non-monotone submodular maximization," Journal of Combinatorial Optimization, Springer, vol. 45(3), pages 1-15, April.
    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. Shaojie Tang & Jing Yuan, 2023. "Beyond submodularity: a unified framework of randomized set selection with group fairness constraints," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-22, May.
    2. Jing Yuan & Shaojie Tang, 2023. "Group fairness in non-monotone submodular maximization," Journal of Combinatorial Optimization, Springer, vol. 45(3), pages 1-15, April.

    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:inm:orijoc:v:36:y:2024:i:2:p:359-376. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.