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

DOI10.1016/0020-0190(86)90123-7zbMATH Open0604.90111OpenAlexW2016574553MaRDI QIDQ1083370FDOQ1083370

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

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

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)

Cites Work

• Title not available (Why is that?)
• Probabilistic analysis of the subset-sum problem
• Title not available (Why is that?)

Cited In (4)

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

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)