New Approaches for Optimizing over the Semimetric Polytope