Exponential Algorithms for Knapsack

Recomm. for undergrads: yes
Posted by: dick lipton
on: February 4th, 2009

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. 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}$?

\end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

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


* indicates original appearance(s) of problem.

References

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

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

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

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

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?

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?

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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.