Additive Combinatorics, Subset Sum, and Knapsack
毛宇尘，4 月 13 日 14:00
In recent years, there has been significant progress in Subset Sum and Knapsack, and most of the works rely on additive combinatorics to prove structural property for a dense set (or a dense group of sets). One particular theorem used in these works is that when a subset of \(\{1,2,3, \ldots, w\}\) contains \(\widetilde{\Omega}(\sqrt{w})\) distinct integers, the collection of its subset sums must contain a long arithmetic progression. Using the theorem, it can be shown that certain instances of Subset Sum (the so-called dense subset sum) can be solved in linear time [Galil\&Margalit'91, Bringmann\&Wellnitz’21]. We realized that this property could also be used to solve Knapsack and proposed an \(\widetilde{O}(n + w^{12/5})\)-time exact algorithm, where \(w\) is the maximum weight of items, as well as an \(\widetilde{O}(n + (1/\varepsilon)^2)\)-time FPTAS. The exact algorithm was later improved to \(\widetilde{O}(n + w^2)\) independently by [Jin’24 and Bringmann’24]. Both of the exact algorithm and the FPTAS match a conditional lower bound.
There is a related but more flexible theorem from additive combinatorics stating that when a group of subsets of \(\{1,2,\ldots, w\}\) have a total size of \(\widetilde{\Omega}(w)\), their sumset contains a long arithmetic progression. With this theorem, we propose an \(\widetilde{O}(n + 1/\varepsilon)\)-time FPTAS for Parititon (a special case of Subset Sum) and an \(\widetilde{O}(n + \sqrt{wt})\)-time exact algorithm for Subset Sum.
In this talk, I will give a high-level overview of how additive combinatorics is used to solve Subset Sum and Knapsack. This is based on an ongoing work and our recent works in SODA’24 and STOC’24. All are joint works with Lin Chen, Jiayi Lian, and Guochuan Zhang.