The bounded subset sum problem is almost everywhere randomly decidable in O(n)

DOI10.1016/0020-0190(86)90123-7MaRDI QIDQ1083370zbMATH OpenOpenAlexFDO

Authors H. Schreck, Gottfried Tinhofer

Publication date 1986

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(86)90123-7

zbMATH Keywords

A-bounded subset sum problemrandomized greedy algorithmsubset sum problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09) Combinatorial optimization (90C27)

Review text

The subset sum problem is to decide, whether for given positive integers b, \(a_ i\), \(1\leq i\leq n\) the equation \[ (SS)\quad b=\max \{\sum a_ ix_ i| \sum a_ ix_ i\leq b,\quad x_ i\in \{0,1\},\quad 1\leq i\leq n\} \] is true. Given a sequence \(A=(A_ n)_{n\in N}\) of positive integers with \(A_ n=o(n)\) the A-bounded subset sum problem SS(A) is the set of all problem instances of type (SS) with \(a_ i\in \{1,...,A_ n\}\) and \(b\in \{1,...,nA_ n\}\). We show that for each A-bounded subset sum problem SS(A) an 0(n) randomized greedy algorithm finds the correct maximum with probability 1/2 for almost all problem instances. Hence the A-bounded subset sum problem is almost everywhere randomly decidable in 0(n).

Recommendations

• A Fast Approximation Algorithm for the Subset-sum Problem
• A Fast Approximation Algorithm For The Subset-Sum Problem
• Succinct Certificates for Almost All Subset Sum Problems
• Stochastic analysis of greedy algorithms for the subset sum problem
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

Cites work

• scientific article; zbMATH DE number 3174053 (Why is no real title available?)
• scientific article; zbMATH DE number 3693147 (Why is no real title available?)
• Probabilistic analysis of the subset-sum problem

Cited in

(4)

• Subset sum in the absence of concentration
• The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem
• Succinct Certificates for Almost All Subset Sum Problems
• An exact algorithm for the subset sum problem

This page was built for publication: The bounded subset sum problem is almost everywhere randomly decidable in O(n)

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