arXiv Artificial Intelligence· Trung Thanh Nguyen, Khaled Elbassioni, J\"{o}rg Rothe·· 18 小时前AI 评分22
加权最大最小份额分配杂务的近似界改进
Improving the Bounds on Approximating Weighted Maximin Share for Chores
AI 导读
针对任意正权重、加性非负成本函数下的不可分割杂务分配问题，研究证明每个实例都存在 4.124234528-WMMS 公平分配，并对权重与成本均为二进制有理数的实例给出多项式时间算法，可计算 4.12424-WMMS 分配。研究还构造出一族成本严格为正且同序的实例，其最优 WMMS 近似因子收敛于 e，从而将此前 Li 等人给出的 [2,12] 区间收窄至 [e,4.12424]。
来源：arXiv Artificial Intelligence · arxiv.org