1 |
Analysis of the Probabilistic Algorithms for Solving Subset Sum ProblemLin, Shin-Hong 11 August 2005 (has links)
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.
|
Page generated in 0.0333 seconds