摘要
研究了带背包约束的基数公平分配问题,即将给定的n个物品放入m个背包,在不超过背包容量的情况下,使得背包中装入的最小物品数尽可能大.通过预处理,可以假定每一个实例的最优值为k且n=km.得到如下的结果:①当所有背包的容量均相同时,通过对3-划分问题的归约证明了该问题不存在近似比大于2/3的近似算法,并基于贪婪法给出一个目标函数至少为k-1的近似算法;②当背包的容量不等时,通过对,维数值匹配问题的归约证明了该问题不存在近似比大于1/2的近似算法,并基于线性规划取整算法给出一个目标函数至少为k-2的近似算法.
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 2/3 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 1/2 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.
作者
王浩
刘沁玲
李伟东
WANG Hao;LIU Qin-ling;LI Wei-dong(The Second Middle School Affiliated to Yunnan University,Kunming 650091,Yunnan,China;School of Mathematics and Statistics,Yunnan University,Kunming 650504,Yunnan,China)
出处
《云南大学学报（自然科学版）》
CAS
CSCD
北大核心
2021年第2期214-222,共9页
Journal of Yunnan University(Natural Sciences Edition)
基金
国家自然科学基金(61662088),云南省创新团队项目(IRTSTYN).
关键词
背包问题
公平分配
近似算法
贪婪法
迭代取整
knapsack problem
fair allocation
approximation algorithm
greedy algorithm
iterative rounding
