×

Solving dense subset-sum problems by using analytical number theory. (English) Zbl 0686.68030

Summary: Theorems from analytical number theory are used to derive new algorithms for the subset-sum problem. The algorithms work for a large number of variables (m) with values that are bounded above. The bound (\(\ell)\) depends moderately on m. While the dynamic programming approach yields an \(O(\ell m^ 2)\) algorithm, the new algorithms are substantially faster.

MSC:

68Q25 Analysis of algorithms and problem complexity
11P99 Additive number theory; partitions
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahrens, J. H.; Finke, G., Merging and sorting applied to the zero-one knapsack problem, Oper. Res., 23, 1099-1109 (1975) · Zbl 0324.90047
[2] Alon, N.; Freiman, G., On sums of subsets of a set of integers, Combinatorica, 8, 297-306 (1988) · Zbl 0666.10035
[3] Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Oper. Res. 28, 1130-1154 (1980) · Zbl 0449.90064
[4] Berstein, A. A.; Freiman, G. A., Analytical methods of discrete optimization, ZEMJ, 89-105 (1979), [In Russian]
[5] Buzytsky, P. L., An effective formula for the number of solutions of linear Boolean equations, SIAM J. Algebraic Discrete Methods, 3, 182-186 (1982) · Zbl 0491.90071
[6] Buzytsky, P. L.; Freiman, G. A., Analytical methods in integer programming, ZEMJ, 48 (1980), [In Russian] · Zbl 0599.90087
[7] Buzytsky, P. L.; Freiman, G. A., Analytical methods in combinatorial problems, Izv. Acad. Nauk SSSR Ser. Tech. Kibernet., 2, 2-12 (1980), [In Russian]
[8] Buzytsky, P. L.; Freiman, G. A., On a possibility to solve combinatorial problems by analytical methods, Ann. N.Y. Acad. Sci., 337, 103-117 (1980)
[9] Buzytsky, P. L.; Freiman, G. A., Integer programming and number theory, Ann. N.Y. Acad. Sci., 373, 191-201 (1981) · Zbl 0599.90087
[10] Buzytsky, P. L.; Freiman, G. A., An effective formula for the number of solutions of system of two 0.1-equations, Discrete Appl. Math., 6, 127-133 (1983) · Zbl 0524.90062
[11] Buzytsky, P. L.; Freiman, G. A., An effective formula for the number of solutions of system of 0.1-linear equations, Ann. N.Y. Acad. Sci., 410, 83-90 (1983) · Zbl 0599.90088
[12] Chaimovich, M., An efficient algorithm for subset sum problem (1989), submitted for publication
[13] Chaimovich, M., Subset sum problem with different summands: Computation (1989), submitted for publication
[14] Chvatal, V., Hard knapsack problem, Oper. Res., 28, 1402-1411 (1980) · Zbl 0447.90063
[15] Erdös, P.; Freiman, G., On two additive problems, J. Number Theory (1989), in press
[16] Faaland, B., Solution of the valve-independent knapsack problem by partitioning, Oper. Res., 21, 332-337 (1973) · Zbl 0267.90068
[17] Freiman, G. A., An analytical method of analysis of linear Boolean equations, Ann. N.Y. Acad. Sci., 337, 97-102 (1980)
[18] Freiman, G. A., On external additive problems of Paul Erdös, (Proceedings, Canberra Conference of Combinatorics. Proceedings, Canberra Conference of Combinatorics, August 1987. Proceedings, Canberra Conference of Combinatorics. Proceedings, Canberra Conference of Combinatorics, August 1987, ARS Combinatorica B, 26 (1988)), 107-113 · Zbl 0067.27402
[19] Freiman, G. A., Subset sum problem with different summands (1989), submitted for publication · Zbl 0701.90068
[20] Freiman, G. A., New analytical result on subset sum problem, (Proceedings, French-Israeli Conference on Combinatorics and Algorithms. Proceedings, French-Israeli Conference on Combinatorics and Algorithms, November 1988 (1989)), in press · Zbl 0937.11500
[21] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039
[22] Lagarias, J.; Odlyzko, A., Solving low-density subset sums, (Proceedings, 24th IEEE Symposium on Foundations of Computer Science (1983)), 1-10
[23] Lipkin, E., On representation of r-powers by subset sums, Acta Arith. (1989), in press · Zbl 0691.10042
[24] Margalit, O., Efficient Elementary Methods for the Dense Subset-Sum Problem, (M.Sc. thesis (1988), Computer Science Department, Tel-Aviv University)
[25] Martello, S.; Toth, P., A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Management Sci., 30, no. 6 (1984), (June) · Zbl 0555.90073
[26] Sarközy, A., Finite addition theorems, II, J. Number Theory (1989), in press · Zbl 0674.10042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.