Open Problem Garden - Exponential Algorithms for Knapsack - Comments

References (re: Exponential Algorithms for Knapsack)

rzwaan — Fri, 06 Aug 2010 11:08:13 +0200

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 (re: Exponential Algorithms for Knapsack)

Anonymous — Tue, 03 Aug 2010 13:48:28 +0200

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 (re: Exponential Algorithms for Knapsack)

Stephen Le Guen — Mon, 29 Mar 2010 16:36:26 +0200

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 (re: Exponential Algorithms for Knapsack)

Anonymous — Sun, 07 Feb 2010 06:01:08 +0100

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 (re: Exponential Algorithms for Knapsack)

Anonymous — Wed, 13 Jan 2010 09:19:43 +0100

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? (re: Exponential Algorithms for Knapsack)

Anonymous — Tue, 08 Sep 2009 19:27:47 +0200

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? (re: Exponential Algorithms for Knapsack)

cwenner — Sat, 04 Apr 2009 22:42:11 +0200

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

Exponential Algorithms for Knapsack

dick lipton — Wed, 04 Feb 2009 14:16:35 +0100

Author(s): Lipton

Subject: Theoretical Comp. Sci. » Algorithms

Conjecture

The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?