2 papers
cs.DS2026
Dense Subset Sum in Multi-Dimension
Lin Chen, Tingwei Hu, Yuchen Mao +1
We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, give…
cs.DS2026
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Lin Chen, Tingwei Hu, Yuchen Mao +5
In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our go…