Succinct Certificates for Almost All Subset Sum Problems

DOI10.1137/0218037MaRDI QIDQ4207577zbMATH OpenOpenAlexFDO

Authors Merrick Furst, R. Kannan

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218037

zbMATH Keywords

latticeNP-completesubset sumshortest vectorcertificates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06)

Recommendations

• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)
• scientific article; zbMATH DE number 176777
• STACS 2005
• Solving low-density subset sum problems

Cited in

(5)

• On the integrality gap of binary integer programs with Gaussian data
• A short note on Merlin-Arthur protocols for subset sum
• Phase transition and finite-size scaling for the integer partitioning problem
• Improved low-density subset sum algorithms
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)

This page was built for publication: Succinct Certificates for Almost All Subset Sum Problems

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