Return to search

Analysis of the Probabilistic Algorithms for Solving Subset Sum Problem

In general, subset sum problem is strongly believed to be computationally difficult to solve.
But in 1983,
Lagarias and Odlyzko proposed a probabilistic algorithm for solving subset sum problems of sufficiently low density
in polynomial time.
In 1991, Coster et. al. improved the Lagarias-Odlyzko algorithm and solved subset sum problems with higher density.
Both algorithms reduce subset sum problem to finding shortest non-zero vectors in special lattices.
In this thesis,
we first proposed a new viewpoint to define the problems which can be solved by this two algorithms
and shows the improved algorithm isn't always better than the Lagarias-Odlyzko algorithm.
Then we verify this notion by experimentation.
Finally, we find that the Lagrias-Odlyzko algorithm can solve the high-density subset sum problems
if the weight of solution is higher than 0.7733n or lower than 0.2267n, even the density is close to 1.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0811105-140024
Date11 August 2005
CreatorsLin, Shin-Hong
ContributorsChun-I Fan, Chun-Hung Richard Lin, D. J. Guan
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageCholon
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0811105-140024
Rightsnot_available, Copyright information available at source archive

Page generated in 0.0019 seconds