Week 6. The Hamming Steiner Tree Problem Revisited.

In trying to find a new approach to the Euclidean Steiner tree problem, this week I revisited hardness of approximability of Hamming Steiner trees. Using a different hard to approximate instance of Vertex Cover with low maximum degree, I was able to get a far improved hardness of approximability constant of $1.0018$, the best known constant. However, managing this required mapping the graph to a triangle-free graph instance. As a corollary, I get the same hardness bound for the $\ell_1$ Steiner tree problem.