Exponential Algorithms for Knapsack

Importance: Medium ✭✭

Author(s):

Subject:	Theoretical Computer Science
	» Algorithms

Keywords:	Algorithm construction
	Exponential-time algorithm
	Knapsack

Recomm. for undergrads: yes

Posted	by:	dick lipton
	on:	February 4th, 2009

Conjecture

The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{1},x_{2},\dots,x_{n}$ so that $\sum_{i=1}^{n} a_{i}x_{i} = b.$ The best known worst-case algorithm runs in time $2^{n/2}$ times a polynomial in $n$ . Is there an algorithm that runs in time $2^{n/3}$ ?

Bibliography

[SS] Richard Schroeppel and Adi Shamir. A T=O(2^n/2), S=O(2^n/4) algorithm for certain NP-complete problems, SIAM J. Comput. 10 (1981), no. 3, 456--464.

* indicates original appearance(s) of problem.

add new comment

References

On August 6th, 2010 rzwaan says:

Solving this problem in pseudopolynomial time with polynomial space: Daniel Lokshtanov and Jesper Nederlof: "Saving Space by Algebraization". To appear in the proceedings of ACM Symposium on Theory of Computing (STOC 2010).

The next reference solves this problem (even general knapsack, I believe). An 2^{0.311 n} Algorithm: Nick Howgrave-Graham and Antoine Joux : "A new generic algorithm for hard knapsacks". To appear in the proceedings of EUROCRYPT 2010.

However, the problem might be easily adjusted to "find an algorithm that takes O(2^{c n}) time, where c < 0.311", etc etc.

Updates

On August 3rd, 2010 Anonymous says:

Publications from 2010 on this topic: Pseudopolynomial algorithm with only polynomial space: Daniel Lokshtanov and Jesper Nederlof: "Saving Space by Algebraization". To appear in the proceedings of ACM Symposium on Theory of Computing (STOC 2010).

Fast knapsack: Nick Howgrave-Graham and Antoine Joux: "New Generic Algorithms for Hard Knapsacks". To appear in the proceedings of EUROCRYPT 2010 The running time is O^*(2^0.311 n), which is faster than the question posted here.

Obviously, the question could become: find a lower constant than 0.311.

0-1 knapsack

On March 29th, 2010 Stephen Le Guen says:

I do not know how to determine the run time but I have an algorithm based on dynamic programming which solves the problem more efficiently than a simple search but not in polynomial time!

I have implemented the procedure as a Java program and tried to express it as a flow chart. Files for both of these are available at; www.cybase.co.uk/wlcs/Software.html

although at the moment the website is down.

I have contacted the ISP to try and restore it.

This appears to be answered

On February 7th, 2010 Anonymous says:

see paper at http://www.joux.biz/publications/Knapsacks.pdf and rjlipton's blog post about it at http://rjlipton.wordpress.com/2010/02/05/a-2010-algorithm-for-the-knapsack-problem/

of course, this is an open ended question, there is still room for better algorithms.

A solution has been announced

On January 13th, 2010 Anonymous says:

A (randomized, probably heuristic) algorithm has been announced to solve this problem in time close to 2^(0.311 n), at the ESC 2010 seminar.

For details, see: https://cryptolux.org/ESC/Antoine_Joux

Subset sum or 0-1?

On September 8th, 2009 Anonymous says:

When your values - your a_n - can be negative, and your b (the goal) is zero, then it's called "subset sum". If the a_n are non-negative (i.e., some of the a's may be zero), the b is positive, and the choice is to either exclude (0) or include (1) one "copy" of each value, then it's a "0-1 knapsack" problem. Usually, but not always, a knapsack problem has components with multiple values, and the goal is a minimax problem: maximize the a's, while minimizing the c's.

It's always darkest, just after the lights go out.

0-1 Knapsack?

On April 4th, 2009 cwenner says:

I know this problem as subset sum and not as 0-1 knapsack.

Open Problem Garden