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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0811105-140024 |
| Date | 11 August 2005 |
| Creators | Lin, Shin-Hong |
| Contributors | Chun-I Fan, Chun-Hung Richard Lin, D. J. Guan |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | Cholon |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0811105-140024 |
| Rights | not_available, Copyright information available at source archive |
Page generated in 0.0018 seconds