Block reduction for arbitrary norms
- We generalize the concept of block reduction for lattice bases from l2-norm to arbitrary norms. This extends the results of Schnorr. We give algorithms for block reduction and apply the resulting enumeration concept to solve subset sum problems. The deterministic algorithm solves all subset sum problems. For up to 66 weights it needs in average less then two hours on a HP 715/50 under HP-UX 9.05.
Author: | Michael Kaib, Harald Ritter |
---|---|
URN: | urn:nbn:de:hebis:30-12451 |
Document Type: | Report |
Language: | English |
Date of Publication (online): | 2005/07/18 |
Year of first Publication: | 1994 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2005/07/18 |
Source: | Technical Report, Universität Frankfurt am Main, 1994. - http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
HeBIS-PPN: | 190083816 |
Institutes: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Licence (German): | Deutsches Urheberrecht |