王浩, 刘沁玲, 李伟东. 带背包约束的基数公平分配问题[J]. 云南大学学报(自然科学版), 2021, 43(2): 214-222. doi: 10.7540/j.ynu.20200102
引用本文: 王浩, 刘沁玲, 李伟东. 带背包约束的基数公平分配问题[J]. 云南大学学报(自然科学版), 2021, 43(2): 214-222. doi: 10.7540/j.ynu.20200102
WANG Hao, LIU Qin-ling, LI Wei-dong. The cardinality fair allocation problem with knapsack constraints[J]. Journal of Yunnan University: Natural Sciences Edition, 2021, 43(2): 214-222. DOI: 10.7540/j.ynu.20200102
Citation: WANG Hao, LIU Qin-ling, LI Wei-dong. The cardinality fair allocation problem with knapsack constraints[J]. Journal of Yunnan University: Natural Sciences Edition, 2021, 43(2): 214-222. DOI: 10.7540/j.ynu.20200102

带背包约束的基数公平分配问题

The cardinality fair allocation problem with knapsack constraints

  • 摘要: 研究了带背包约束的基数公平分配问题,即将给定的 n 个物品放入 m 个背包,在不超过背包容量的情况下,使得背包中装入的最小物品数尽可能大. 通过预处理,可以假定每一个实例的最优值为 kn = km. 得到如下的结果:①当所有背包的容量均相同时,通过对3-划分问题的归约证明了该问题不存在近似比大于 \dfrac23 的近似算法,并基于贪婪法给出一个目标函数至少为 k - 1 的近似算法;②当背包的容量不等时,通过对3维数值匹配问题的归约证明了该问题不存在近似比大于 \dfrac12 的近似算法,并基于线性规划取整算法给出一个目标函数至少为 k - 2 的近似算法.

     

    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.

     

/

返回文章
返回