13th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms

/
Haifa.JPG

I've just given a talk at the 13th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, on our new paper, "Finding the Minimum-Weight k-path" (to appear in WADS 2013). Presentation can be found here.

For those of you who are LaTeX-inclined, here is the abstract: ​

Given a weighted $n$-vertex graph $G$ with integer edge-weights taken from a range $[-M,M]$, we show that the minimum-weight simple path visiting $k$ vertices can be found in time $\tilde{O}(2^k \poly(k) M n^\omega) = O^*(2^k M)$. If the weights are reals in $[1,M]$, we provide a $(1+\varepsilon)$-approximation which has a running time of $\tilde{O}(2^k \poly(k) n^\omega(\log\log M + 1/\varepsilon))$. For the more general problem of $k$-tree, in which we wish to find a minimum-weight copy of a $k$-node tree $T$ in a given weighted graph $G$, under the same restrictions on edge weights respectively, we give an exact solution of running time $\tilde{O}(2^k \poly(k) M n^3) $ and a $(1+\varepsilon)$-approximate solution of running time $\tilde{O}(2^k \poly(k) n^3(\log\log M + 1/\varepsilon))$. All of the above algorithms are randomized with a polynomially-small error probability.

​

​