论文标题
背包问题的团体公平性
Group Fairness for Knapsack Problems
论文作者
论文摘要
我们通过集体公平限制研究背包问题。问题的输入包括一个有界能力和一组项目的背包，每个项目都属于特定类别，具有和相关的重量和价值。这个问题的目的是选择一个项目的子集，以使所有类别都公平地表示，所选项目的总重量不超过背包的容量，并且总值最大。我们研究公平性参数，例如每个类别项目总价值的界限，每个类别的项目的总权重以及每个类别的项目总数。我们为这些问题提供了近似算法。这些公平的概念也可以扩展到Min-Knapsack问题。公平的背包问题包括各种重要问题，例如参与性预算，公平的预算分配，广告。
We study the knapsack problem with group fairness constraints. The input of the problem consists of a knapsack of bounded capacity and a set of items, each item belongs to a particular category and has and associated weight and value. The goal of this problem is to select a subset of items such that all categories are fairly represented, the total weight of the selected items does not exceed the capacity of the knapsack,and the total value is maximized. We study the fairness parameters such as the bounds on the total value of items from each category, the total weight of items from each category, and the total number of items from each category. We give approximation algorithms for these problems. These fairness notions could also be extended to the min-knapsack problem. The fair knapsack problems encompass various important problems, such as participatory budgeting, fair budget allocation, advertising.
