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

DOI10.1016/0020-0190(86)90123-7zbMath0604.90111OpenAlexW2016574553MaRDI QIDQ1083370

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)

Related Items (2)

The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem ⋮ An exact algorithm for the subset sum problem

Cites Work

• Probabilistic analysis of the subset-sum problem
• Unnamed Item
• Unnamed Item

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