改进杂务加权最大最小份额近似界

研究者在不可分家务分配问题中证明，任意权重和可加非负成本函数下，每个实例都存在 4.124234528-WMMS 公平分配。对于权重和成本为二进制有理数的实例，给出了在智能体数、家务数和输入编码长度上多项式时间的 4.12424-WMMS 分配算法。同时构造了一族最优 WMMS 近似因子收敛到 e 的实例，将此前已知的 [2,12] 区间缩小至 [e,4.12424]。

摘自 arXiv：cs.AI

还没有足够的连续观测数据，暂不绘制趋势。