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

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

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

randomized greedy algorithmsubset sum problemA-bounded subset sum problem

Mathematics Subject Classification ID

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

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)

• An exact algorithm for the subset sum problem
• 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

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)