4 papers
Restricted Max-Min Allocation: Approximation and Integrality Gap
Siu-Wing Cheng, Yuchen Mao
Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most . However, their proof does not give…
The diophantine exponent of the points of
Mostafa W. Hassan, Yuchen Mao, Naser T. Sardari +2
Assume a polynomial-time algorithm for factoring integers, Conjecture~\ref{conj}, and and are prime numbers, where for some . We develop a polyn…
Integrality Gap of the Configuration LP for the Restricted Max-Min Fair Allocation
Siu-Wing Cheng, Yuchen Mao
The max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. Each player has a non-negative va…
Restricted Max-Min Fair Allocation
Siu-Wing Cheng, Yuchen Mao
The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approxima…