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.