Abstract:
Given
n
items and
m
knapsacks, the cardinality fair allocation problem with knapsack constraints is to pack the items into the knapsacks, such that the minimum number of items packed into each knapsack is maximized, without exceeding the capacities of the knapsacks. Assuming that the optimal value of any input instance is
k
and
n = km
, the following results are obtain: ① when all the capacities of knapsacks are equal, this problem cannot be approximated better than
\dfrac23
by reduction from 3-partition, and a greedy algorithm is proposed to find a feasible solution with objective value at least
k - 1
. ② when all the capacities of knapsacks are not equal, this problem cannot be approximated better than
\dfrac12
by reduction from 3-dimensional numerical matching, and an iterative rounding algorithm is proposed to find a feasible solution with objective value at least
k - 2
.