Home

An FPTAS for 7/9-Approximation to Maximin Share Allocations


Speaker

Xin Huang, Kyushu University

Time

2025-11-28 16:00:00 ~ 2025-11-28 17:00:00

Location

软件大楼专家楼1319会议室

Host

陶表帅

Abstract
We present a new algorithm that achieves a (7/9)-approximation for the maximin share (MMS) allocation of indivisible goods under additive valuations, improving the current best ratio of 10/13 (Heidari et al., SODA 2026). Building on a new analytical framework, we further obtain an FPTAS that achieves a(7/9 - ε)approximation in 1/ε·poly(n,m) time. Compared with prior work (Heidari et al., SODA 2026), our algorithm is substantially simpler.
Bio
Xin Huang is currently an Assistant Professor at Kyushu University. He obtained his Ph.D. from The Chinese University of Hong Kong in 2020. From 2020 to 2023, he was a postdoctoral researcher at Technion, Israel. His research focuses on fair division problems.
© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University
分享到

地址:上海市东川路800号上海交通大学软件大楼专家楼
邮箱:jhc@sjtu.edu.cn 电话:021-54740299
邮编:200240