Fairness k-Submodular Maximization Subject to Matroid Constraint

Tan D. Tran; Canh V. Pham; Phuong N. H. Pham

IJCAI 20260 citations

Fairness k-Submodular Maximization Subject to Matroid Constraint

Tan D. Tran, Canh V. Pham, Phuong N. H. Pham

Abstract

Fairness k-submodular maximization has attracted increasing interest due to its broad relevance in artificial intelligence and machine learning. However, most existing work is limited to monotone objectives or simple size constraints, while the non-monotone setting with richer constraints remains largely unexplored. In this paper, we first introduce a constant-ratio approximation algorithm for the problem under a general non-monotone objective function and a matroid constraint. Our approach is built upon a two-stage algorithmic framework. Specifically, we first develop an algorithm that guarantees feasibility with respect to upper fairness bounds only. We then show how this algorithm can be systematically extended to simultaneously enforce fairness bounds, while preserving provable approximation guarantees. Comprehensive experiments on standard benchmark datasets demonstrate that our algorithm achieves high-quality objective values while maintaining a favorable balance between fairness guarantees and query efficiency consistently outperforming existing state-of-the-art methods.

Constraint Satisfaction and Optimization: Constraint learning and acquisitionConstraint Satisfaction and Optimization: Constraint optimization problemsConstraint Satisfaction and Optimization: Constraint satisfactionMachine Learning: Learning theoryMachine Learning: Optimization

BibTeX

@inproceedings{ijcai2026_fairnessksubmodu,
  title = {Fairness k-Submodular Maximization Subject to Matroid Constraint},
  author = {Tan D. Tran and Canh V. Pham and Phuong N. H. Pham},
  booktitle = {IJCAI 2026},
  year = {2026}
}