Fair Submodular Maximization over a Knapsack Constraint

Lijun LI, Chenyang XU, Liuyi YANG, Ruilong ZHANG

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

Abstract

We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a weight and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total weight does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint).

While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem -- without relaxing either the knapsack or fairness constraints -- remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of $(1-1/e-\epsilon)$ can be obtained in expectation for any $\epsilon >0$.
Original languageEnglish
Title of host publication34th International Joint Conference on Artificial Intelligence (IJCAI 2025)
Publication statusAccepted/In press/Filed - 29 Apr 2025
Event34th International Joint Conference on Artificial Intelligence (2025) - Montreal, Canada
Duration: 16 Aug 202522 Aug 2025
https://2025.ijcai.org/

Conference

Conference34th International Joint Conference on Artificial Intelligence (2025)
Abbreviated titleIJCAI 2025
Country/TerritoryCanada
CityMontreal
Period16/08/2522/08/25
Internet address

Bibliographical note

Information for this record is provided by the author(s) concerned.

Fingerprint

Dive into the research topics of 'Fair Submodular Maximization over a Knapsack Constraint'. Together they form a unique fingerprint.

Cite this