4 citations · 13 across the 6 of their papers we have counts for
5 papers · 1 filter
A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in time. This improves…
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity wit…
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…
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…