Subset-sum problems with different summands: Computation

DOI10.1016/0166-218X(90)90071-JMaRDI QIDQ922292zbMATH OpenOpenAlexFDO

Authors Mark Chaimovich

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(90)90071-j

zbMATH Keywords

subset-sum problem

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Review text

Let \(A=\{a_ 1,...,a_ m\}\), \(a_ i\in N\), \(a_ i\leq l\) and let \(A^*\) be a set of subset sums, i.e., \(A^*=\{S_ B| S_ B=\sum_{a_ i\in B}a_ i\), \(B\subseteq A\}\). The subset-sum problem (SSP) can be formulated as follows: find a maximal subset sum \(S\in A^*\) such that \(S\leq M\), where M is any given positive number. The interesting paper presents two algorithms for SSP with different summands which are based on analytical results of number theory. The first one improves the time bound of one of Freiman's algorithm to O(m log m), the time bound of the second algorithm is O(m).

Recommendations

• scientific article; zbMATH DE number 4149895
• The subset sum problem
• A Fast Approximation Algorithm for the Subset-sum Problem
• On variations of the subset sum problem
• A Fast Approximation Algorithm For The Subset-Sum Problem

Cites work

• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• scientific article; zbMATH DE number 4149895 (Why is no real title available?)
• scientific article; zbMATH DE number 4089636 (Why is no real title available?)
• scientific article; zbMATH DE number 3719153 (Why is no real title available?)
• scientific article; zbMATH DE number 1315279 (Why is no real title available?)
• On representation of r-th powers by subset sums
• On sums of subsets of a set of integers
• On two additive problems

Cited in

(12)

• On variations of the subset sum problem
• Subset sum problems with digraph constraints
• The complexity of unary subset sum
• The subset sum problem
• scientific article; zbMATH DE number 4149895 (Why is no real title available?)
• scientific article; zbMATH DE number 1315279 (Why is no real title available?)
• scientific article; zbMATH DE number 553907 (Why is no real title available?)
• The interval subset sum problem
• An asymptotic formula for the cardinality of a difference subset of the multidimensional torus \(\mathbb{Z}_3^n\)
• scientific article; zbMATH DE number 7688183 (Why is no real title available?)
• Fast exact and approximate algorithms for k-partition and scheduling independent tasks
• Estimating the cardinality of a difference subset of the discrete multi-torus \(\mathbb Z_3^n\)

This page was built for publication: Subset-sum problems with different summands: Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922292)