Chaimovich, Mark On solving dense \(n\)-dimensional subset sum problems. (English) Zbl 0759.90071 Combinatorics, graph theory, and computing, Proc. 22nd Southeast Conf., Baton Rouge/LA (USA) 1991, Congr. Numerantium 84, 41-49 (1991). Summary: [For the entire collection see Zbl 0747.00035.]In this research the conditions are determined whereby the \(n\)- dimensional Subset Sum Problem can be solved using the methods of additive number theory. The result is an extension of the previous work on application of analytical methods to integer programming. This new approach ensures an exact and efficient solution of the problem and provides the design of pseudo-polynomial time algorithms. As an intermediate result the conditions for solvability of the system of \(n\) linear Boolean equations with a large number of variables are determined and the asymptotic formula for the number of its solutions is obtained. Cited in 2 Documents MSC: 90C09 Boolean programming 90C60 Abstract computational complexity for mathematical programming problems 90C10 Integer programming Keywords:\(n\)-dimensional subset sum problem; additive number theory; pseudo- polynomial time algorithms Citations:Zbl 0747.00035 × Cite Format Result Cite Review PDF