Multidimensional subset sum problem

Show full item record

Title: Multidimensional subset sum problem
Author: Kolesnikov, Vladimir
Abstract: This thesis explores new modifications to the successful LLL approach to solving the Subset Sum problem. This work is an optimization of the matrix representation of an instance. Traditionally, the basis matrix contained only one column with set elements and the sum. In this thesis we suggest having several data columns (thus introducing multidimensionality). This allows us to reduce the size of coulmn entries which changes the complexity of the problem. Splitting the data into multiple columns greatly simplifies the task of solving the Subset Sum problem. However, other problems arise when we try to generate multiple columns. Here we try to find the optimal way to do the split and present the results. Our main goal was to try to solve the current hardest Subset Sum problem instances: the ones with density slightly greater than 1. Dramatic improvement in the rate of success was observed (up to 1500 %) compared to one- dimensional implementations.
Record URI: http://hdl.handle.net/1850/12328
Date: 1997

Files in this item

Files Size Format View
VKolesnikovThesis09-03-1997.pdf 983.9Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse