Open Problem Garden

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

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

Streinu, Ileana

arrangement graph

graph coloring

Graph Theory » Topological G.T. » Coloring

3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.