Multidimensional subset sum problem

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
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:
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