Algorithms and complexity results for the 0–1 knapsack problem with group fairness
Open Access
- 6 October 2025
- journal article
- research article
- Published by Springer Nature in Optimization Letters
- Vol. 20 (3) , 577-594
Abstract
This paper presents an exact algorithm for a generalisation of the classical 0–1 Knapsack Problem, called the Knapsack Problem with Group Fairness. In this problem, items are partitioned into classes, and fairness constraints affect the number of items that can or must be chosen from each class. The problem was introduced by Patel et al. (in: Dignum (eds) Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 2021), where approximation algorithms are discussed. This paper describes the first exact solution approaches for the Knapsack Problem with Group Fairness, based on integer linear programming formulations and a dynamic programming algorithm. The latter allows us to establish the complexity of the problem. Finally, a set of computational experiments on benchmark instances derived from the knapsack literature compare the effectiveness of the alternative solution approaches.Keywords
Funding Information
- Universitat Pompeu Fabra
This publication has 35 references indexed in Scilit:
- A Technopolitical Network for Participatory Democracy: The Future of a Collective Platform2024
- The Price of Fairness for Indivisible GoodsTheory of Computing Systems, 2021
- An iterative algorithm for the Max-Min knapsack problem with multiple scenariosOperational Research, 2019
- The knapsack problem with a minimum filling constraintNaval Research Logistics (NRL), 2013
- Efficient and fair routing for mesh networksMathematical Programming, 2010
- Reformulation and Decomposition of Integer Programs2009
- A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraintAnnals of Operations Research, 2008
- The Multiple-Choice Knapsack Problem2004
- A minimal algorithm for the multiple-choice knapsack problemEuropean Journal of Operational Research, 1995
- Equity, envy, and efficiencyJournal of Economic Theory, 1974