Thore Husfeldt
News
New paper at ICALP 2008
We found a way of analysing the classical dynamic programming solution to the TSP of Bellman and Held–Karp using a beautiful lemma of Shearer. This leads to running times (slightly) faster than within a polynomial factor of 2n. The ICALP committee was so kind as to accept this to the forthcoming Iceland ICALP; you can find the submitted manuscript among my on-line papers. This is joint work with Björklund, Kaski, and Koivisto.
What makes this extra fun is that the xkcd web-comic just ran a strip on the dynamic programming algorithm, so I hasten to supply an alternative final frame for it.
Wed, 09 Apr 2008 | Category: News | Permanent link