Combinatorial algorithm for optimization over semimetric polytope
Yes: the dual is a multicommodity flow problem which can be solved using the Garg-Koenemann algorithm http://dx.doi.org/10.1137/S0097539704446232.