加性组合在若干经典组合优化问题中的应用

doi:10.15960/j.cnki.issn.1007-6093.2025.03.010

Abstract

Abstract:

We investigate fundamental combinatorial optimization problems, including the knapsack problem, the subset sum problem and the convolution problem. We want to explore algorithms that achieve the best possible running time, that is, algorithms whose running time is the best possible under standard complexity assumptions. In recent years, important algorithmic progress has been achieved in classic combinatorial optimization problems via additive combinatorics tools. In particular, for several variants of the knapsack problem and subset sum problem researchers have obtained pseudopolynomial time algorithms and polynomial time approximation schemes whose running time almost matches their lower bounds. This paper will survey several important results along this research line, showing the relevance between additive combinatorics and discrete optimization. In particular, we will present: (ⅰ) the finite addition theorem and its application in the algorithmic design for the knapsack problem and the subset sum problem; (ⅱ) Szemerédi-Vu sumset theorem and its application in the algorithmic design for the subset sum problem; and (ⅲ) Balog-Szemerédi-Gowers theorem and its application in the algorithmic design for the bounded monotone (min, +)-convolution problem.

Key words: pseudopolynomial time algorithm, polynomial time approximation scheme, knapsack, subset sum, additive combinatorics

CLC Number:

O221.7

Lin CHEN. Application of additive combinatorics in several classic combinatorial optimization problems[J]. Operations Research Transactions, 2025, 29(3): 202-222.

Figures/Tables 5

References 59

1	GareyM R,JohnsonD S.Computers and Intractability[M].San Francisco:W.H. Freeman Company,1979.
2	NakosV.Nearly optimal sparse polynomial multiplication[J].IEEE Transactions on Information Theory,2020,66(11):7231-7236. doi: 10.1109/TIT.2020.2989385
3	Bringmann K, Fischer N, Nakos V. Sparse nonnegative convolution is equivalent to dense nonnegative convolution [C]//53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021: 1711-1724.
4	SárközyA.Finite addition theorems, Ⅰ[J].Journal of Number Theory,1989,32(1):114-130. doi: 10.1016/0022-314X(89)90102-9
5	SárközyA.Fine Addition Theorems, Ⅱ[J].Journal of Number Theory,1994,48(2):197-218. doi: 10.1006/jnth.1994.1062
6	LevV F.Blocks and progressions in subset sum sets[J].Acta Arithmetica,2003,106(2):123-142. doi: 10.4064/aa106-2-3
7	SzemerédiE,VuV H.Finite and infinite arithmetic progressions in sumsets[J].Annals of Mathematics,2006,163(1):1-35. doi: 10.4007/annals.2006.163.1
8	Karp R M. Reducibility among combinatorial problems [M]//Miller R E, Thatcher J W, Bohlinger J D. (eds. )Complexity of Computer Computations, Boston: Springer, 1972: 85-103
9	BellmanR.Dynamic Programming[M].Princeton:Princeton University Press,1957.
10	PisingerD.Linear time algorithms for knapsack problems with bounded weights[J].Journal of Algorithms,1999,33(1):1-14. doi: 10.1006/jagm.1999.1034
11	TamirA.New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems[J].Operations Research Letters,2009,37(5):303-306. doi: 10.1016/j.orl.2009.05.003
12	KellererH,PferschyU.Improved dynamic programming in connection with an FPTAS for the knapsack problem[J].Journal of Combinatorial Optimization,2004,8(1):5-11. doi: 10.1023/B:JOCO.0000021934.29833.6b
13	Bateni M H, Hajiaghayi M T, Seddighin S, et al. Fast algorithms for knapsack via convolution and prediction [C]//50th Annual ACM SIGACT Symposium on Theory of Computing, 2018: 1269-1282.
14	Axiotis K, Tzamos C. Capacitated dynamic programming: Faster knapsack and graph algorithms [C]//46th International Colloquium on Automata, Languages, and Programming, 2019, 19: 1-13.
15	EisenbrandF,WeismantelR.Proximity results and faster algorithms for integer programming using the Steinitz Lemma[J].ACM Transactions on Algorithms,2019,16(1):1-14.
16	Polak A, Rohwedder L, Wȩgrzycki K. knapsack and subset sum with small items [C]//48th International Colloquium on Automata, Languages, and Programming, 2021, 106: 1-19.
17	Bringmann K, Cassis A. Faster 0-1-knapsack via near-convex min-plus-convolution [C]//31 st Annual European Symposium on Algorithms, 2023, 24 1-16.
18	Chen L, Lian J, Mao Y, et al. Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results [C]//35th Annual ACM-SIAM Symposium on Discrete Algorithms, 2024: 4828-4848.
19	Bringmann K. Knapsack with small items in near-quadratic time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 259-270.
20	Jin C. 0-1 knapsack in nearly quadratic time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 271-282.
21	CyganM,MuchaM,WȩgrzyckiK,et al.On problems equivalent to (min, +)-convolution[J].ACM Transactions on Algorithms,2019,15(1):1-25.
22	Künnemann M, Paturi R, Schneider S. On the fine-grained complexity of one-dimensional dynamic programming [C]//44th International Colloquium on Automata, Languages, and Programming, 2017, 21: 1-15.
23	SahniS.Approximate algorithms for the 0/1 knapsack problem[J].Journal of the ACM,1975,22(1):115-124. doi: 10.1145/321864.321873
24	IbarraO H,KimC E.Fast approximation algorithms for the knapsack and sum of subset problems[J].Journal of the ACM,1975,22(4):463-468. doi: 10.1145/321906.321909
25	LawlerE L.Fast approximation algorithms for knapsack problems[J].Mathematics of Operations Research,1979,4(4):339-356. doi: 10.1287/moor.4.4.339
26	Rhee D. Faster fully polynomial approximation schemes for knapsack problems [D]. Massachusetts Institute of Technology, 2015.
27	Chan T M. Approximation schemes for 0-1 knapsack [C]//1st Symposium on Simplicity in Algorithms, 2018, 5: 1-12.
28	Jin C. An improved FPTAS for 0-1 knapsack [C]//Proceedings of 46th International Colloquium on Automata, Languages, and Programming, 2019, 76: 1-14.
29	Deng M, Jin C, Mao X. Approximating knapsack and partition via dense subset sums [C]//34th Annual ACM-SIAM Symposium on Discrete Algorithms, 2023: 2961-2979.
30	Chen L, Lian J, Mao Y, et al. A nearly quadratic-time FPTAS for knapsack [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 283-294.
31	Mao X. (1-ε)-approximation of knapsack in nearly quadratic time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 295-306.
32	VaziraniV V.Approximation Algorithms[M].Heidelberg:Springer,2001.
33	AggarwalA,KlaweM M,MoranS,et al.Geometric applications of a matrix-searching algorithm[J].Algorithmica,1987,2(1):195-208.
34	Bringmann K, Wellnitz P. On near-linear-time algorithms for dense subset sum [C]//2nd ACM-SIAM Symposium on Discrete Algorithms, 2021: 1777-1796.
35	SzemerédiE,VuV.Long arithmetic progressions in sumsets: Thresholds and bounds[J].Journal of the American Mathematical Society,2005,19(1):119-169. doi: 10.1090/S0894-0347-05-00502-3
36	Bringmann K, Nakos V. A Fine-Grained perspective on approximating subset sum and partition [C]//32nd ACM-SIAM Symposium on Discrete Algorithms, 2021: 1797-1815.
37	AbboudA,BringmannK,HermelinD,et al.SETH-based lower bounds for subset sum and bicriteria path[J].ACM Transactions on Algorithms,2022,18(1):1-22.
38	Gens G V, Levner E V. Fast approximation algorithms for knapsack type problems [C]//Optimization Techniques, Lecture Notes in Control and Information Sciences, 1980: 185-194.
39	Mucha M, WȨgrzycki K, Włodarczyk M. A Subquadratic Approximation Scheme for Partition [C]//30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019: 70-88.
40	Wu X, Chen L. Improved approximation schemes for (un-)bounded subset-sum and partition [EB/OL]. [2025-03-14]. arXiv: 221202883
41	Chen L, Lian J, Mao Y, et al. Approximating partition in near-linear time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 307-318.
42	Karp R M. The fast approximate solution of hard combinatorial problems [C]//6th South-Eastern Conf Combinatorics, Graph Theory and Computing, 1975: 15-31.
43	GensG V,LevnerE V.Approximation algorithm for some scheduling problems[J].Engrg Cybernetics,1978,6,38-46.
44	Gens G V, Levner E V. Computational complexity of approximation algorithms for combinatorial problems [C]//International Symposium on Mathematical Foundations of Computer Science, 1979.
45	Chen L, Lian J, Mao Y, et al. An improved pseudopolynomial time algorithm for subset sum [C]//65th Symposium on Foundations of Computer Science, 2024.
46	FrǐmanG A.Foundations of a Structual Theory of Set Addition[M].Providence:American Mathematical Society,1973.
47	TaoT,VuV H.Additive Combinatorics[M].Cambridge:Cambridge University Press,2006.
48	BalogA,SzemerédiE.A statistical theorem of set addition[J].Combinatorica,1994,14(3):263-268.
49	GowersW T.A new proof of Szemerédi's theorem[J].Geometric & Functional Analysis GAFA,2001,11(3):465-588.
50	Balog A. Many additive quadruples [C]//Proceedings and Lecture Notes in Additive Combinatorics, 2007, 43: 10.
51	SudakovB,SzemerédiE,VuV.On a question of erdős and moser[J].Duke Mathematical Journal,2005,126(1):129-155.
52	Bremner D, Chan T M, Demaine E D, et al. Necklaces, convolutions, and x+y [C]//14th Annual European Symposium, 2006: 160-171.
53	Williams R. Faster all-pairs shortest paths via circuit complexity [C]//46th annual ACM symposium on Theory of computing, 2014: 664-673.
54	Chan T M, Lewenstein M. Clustered integer 3SUM via additive combinatorics [C]//47th annual ACM symposium on Theory of computing, 2015: 31-40.
55	Chi S, Duan R, Xie T, et al. Faster min-plus product for monotone instances [C]//54th Annual ACM SIGACT Symposium on Theory of Computing, 2022: 1529-1542.
56	He Q, Xu Z. Simple and faster algorithms for knapsack [C]//7th Symposium on Simplicity in Algorithms, 2024: 56-62.
57	Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum [C]//28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017: 1073-1084.
58	KellererH,MansiniR,PferschyU,et al.An efficient fully polynomial approximation scheme for the Subset-Sum Problem[J].Journal of Computer and System Sciences,2003,66(2):349-370.
59	Bringmann K, Dürr A, Polak A. Even faster knapsack via rectangular monotone min-plus convolution and balancing [C]//32nd Annual European Symposium on Algorithms, 2024, 33: 1-15.

背包问题	参考文献
$ \widetilde{O}(nt) $	Bellman^[9]
$ O(n\cdot w_{\max}\cdot p_{\max}) $	Pisinger^[10]
$ O(n^3\cdot w_{\max}^2) $	Tamir^[11]
$ \widetilde{O}(n+w_{\max}\cdot t) $	Kellerer和Pferschy^[12], 以及文献[13-14]
$ \widetilde{O}(n+p_{\max}\cdot t) $	Bateni等^[13]
$ \widetilde{O}(n\cdot w_{\max}^2\cdot\min\{n, w_{\max}\}) $	Bateni等^[13]
$ \widetilde{O}(n\cdot\min\{w_{\max}^2, p_{\max}^2\}) $	Eisenbrand和Weismantel^[15], Axiotis和Tzamos^[14]
$ {O}(n+\min\{w_{\max}^3, p_{\max}^3\}) $	Polak等^[16]
$ \widetilde{O}(n\cdot \min\{w_{\max}\cdot p_{\max}^{2/3}, p_{\max}\cdot w_{\max}^{2/3}\}) $	Bringmann和Cassis^[17]
$ \widetilde{O}(n +\min\{w_{\max}^{12/5}, p_{\max}^{12/5}\}) $	Chen等^[18]
$ \widetilde{O}(n +\min\{w_{\max}^{2}, p_{\max}^{2}\}) $	Bringmann^[19], Jin^[20]

背包问题	参考文献
$ n^{O(\frac{1}{ \varepsilon})} $	Sahni^[23]
$ {O}(n\log n+(\frac{1}{ \varepsilon})^4\log \frac{1}{ \varepsilon}) $	Ibarra和Kim^[24]
$ {O}(n\log n+(\frac{1}{ \varepsilon})^4) $	Lawler^[25]
$ O(n\log \frac{1}{ \varepsilon}+(\frac{1}{ \varepsilon})^3\log^2\frac{1}{ \varepsilon}) $	Kellerer和Pferschy^[12]
$ O(n\log \frac{1}{ \varepsilon}+(\frac{1}{ \varepsilon})^{5/2}\log^3\frac{1}{ \varepsilon}) $	Rhee^[26]
$ O(n\log \frac{1}{ \varepsilon}+(\frac{1}{ \varepsilon})^{12/5}/2^{\Omega\left(\sqrt{\log (\frac{1}{ \varepsilon})}\right)}) $	Chan^[27]
$ O(n\log \frac{1}{ \varepsilon}+(\frac{1}{ \varepsilon})^{9/4}/2^{\Omega\left(\sqrt{\log (\frac{1}{ \varepsilon})}\right)}) $	Jin^[28]
$ \widetilde{O}(n+(\frac{1}{ \varepsilon})^{11/5}/2^{\Omega(\sqrt{\log (\frac{1}{ \varepsilon})})}) $	Deng等^[29]
$ \widetilde{O}(n + (\frac{1}{ \varepsilon})^2) $	Chen等^[30], Mao^[31]

划分问题	参考文献
$ O(\frac{n}{ \varepsilon}^2) $	Ibarra和Kim^[24], Karp^[42]
$ O(\frac{n}{ \varepsilon}) $	*Gens和Levner^[43-44]
$ O(n + (\frac{1}{ \varepsilon})^4) $	*Lawler^[25]
$ \widetilde{O}(n + (\frac{1}{ \varepsilon})^2) $	Gens和Levner^[38]
$ \widetilde{O}(n+(\frac{1}{ \varepsilon})^{5/3}) $	Mucha等^[39]
$ \widetilde{O}(n+(\frac{1}{ \varepsilon})^{3/2}) $	Bringmann和Nakos^[36]
$ \widetilde{O}(n + (\frac{1}{ \varepsilon})^{5/4}) $	Deng等^[29], Wu和Chen^[40]
$ \widetilde{O}(n + \frac{1}{ \varepsilon}) $	Chen等^[41]

[1]	ZHANG Yuzhong, LI Shuguang. Scheduling with tree-hierarchical processing set restrictions [J]. Operations Research Transactions, 2020, 24(4): 107-112.
[2]	FAN Jing, LU Xiwen. Supply chain scheduling problem under simple linear deterioration on a single-machine with an unavailability constraint [J]. Operations Research Transactions, 2016, 20(4): 69-76.
[3]	ZHANG Yuzhong, YANG Xiaoguang. The continuity properties of optimal value function of discrete optimization problems [J]. Operations Research Transactions, 2016, 20(3): 79-84.
[4]	ZHU Tingting, CHEN Wei, CHEN Juanjuan, SUN Wenhao. Direct algorithm for continuous separable Knapsack problem [J]. Operations Research Transactions, 2013, 17(1): 44-58.

Application of additive combinatorics in several classic combinatorial optimization problems

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 59

Related Articles 4

Recommended Articles

Metrics

Comments