Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

11 pages, 1 figure

Scientific paper

10.1007/978-3-540-69311-6_31

The subset sum problem (SSP) can be briefly stated as: given a target integer $E$ and a set $A$ containing $n$ positive integer $a_j$, find a subset of $A$ summing to $E$. The \textit{density} $d$ of an SSP instance is defined by the ratio of $n$ to $m$, where $m$ is the logarithm of the largest integer within $A$. Based on the structural and statistical properties of subset sums, we present an improved enumeration scheme for SSP, and implement it as a complete and exact algorithm (EnumPlus). The algorithm always equivalently reduces an instance to be low-density, and then solve it by enumeration. Through this approach, we show the possibility to design a sole algorithm that can efficiently solve arbitrary density instance in a uniform way. Furthermore, our algorithm has considerable performance advantage over previous algorithms. Firstly, it extends the density scope, in which SSP can be solved in expected polynomial time. Specifically, It solves SSP in expected $O(n\log{n})$ time when density $d \geq c\cdot \sqrt{n}/\log{n}$, while the previously best density scope is $d \geq c\cdot n/(\log{n})^{2}$. In addition, the overall expected time and space requirement in the average case are proven to be $O(n^5\log n)$ and $O(n^5)$ respectively. Secondly, in the worst case, it slightly improves the previously best time complexity of exact algorithms for SSP. Specifically, the worst-case time complexity of our algorithm is proved to be $O((n-6)2^{n/2}+n)$, while the previously best result is $O(n2^{n/2})$.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-147058

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.