静5青年讲座 | A Reduction from Chores Allocation to Job Scheduling

A Reduction from Chores Allocation to Job Scheduling

报告人

Dr. Xin Huang

Technion

时  间

2023年10月25日 星期三 2:00pm

地  点

静园五院204

Host

姜少峰 助理教授

 Abstract

We consider allocating indivisible chores among agents with different cost functions, such that all agents receive a cost of at most a constant factor times their maximin share. The state-of-the-art was presented in In EC 2021 by Huang and Lu. They presented a non-polynomial-time algorithm, called HFFD, that attains an 11/9 approximation, and a polynomial-time algorithm that attains a 5/4 approximation.

In this paper, we show that HFFD can be reduced to an algorithm called MultiFit, developed by Coffman, Garey and Johnson in 1978 for makespan minimization in job scheduling. Using this reduction, we prove that the approximation ratio of HFFD is in fact equal to that of MultiFit, which is known to be 13/11 in general, 20/17 for n at most 7, and 15/13 for n=3.

Biography

Xin Huang is a postdoc in the Department of Computer Science at Technion. He received his Ph.D. from the Department of Computer Science and Engineering at The Chinese University of Hong Kong. Before that, he got his bachlor degree from Nanjing University. He works on algorithmic game theory and mainly focus on the fair division problems.

往 期 讲 座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”查看海报