Topology

Atomic reloids are monovalued ★★

Author(s): Porton

Conjecture   Atomic reloids are monovalued.

Keywords: atomic reloid; monovalued reloid; reloid

Posted by porton
updated February 4th, 2009
add new comment
Topology

Composition of atomic reloids ★★

Author(s): Porton

Conjecture   Composition of two atomic reloids is atomic or empty.

Keywords: atomic reloid; reloid

Posted by porton
updated February 4th, 2009
add new comment
Theoretical Comp. Sci. » Algorithms

Exponential Algorithms for Knapsack ★★

Author(s): Lipton

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} $?

Keywords: Algorithm construction; Exponential-time algorithm; Knapsack

Posted by dick lipton
updated August 6th, 2010
7 comments