  Let $\mu$ be a metric on a set T, and let c be a nonnegative function on the
unordered pairs of elements of a superset $V\supseteq T$. We consider the
problem of minimizing the inner product $c\cdot m$ over all semimetrics m on V
such that m coincides with $\mu$ within T and each element of V is at zero
distance from T (a variant of the {\em multifacility location problem}). In
particular, this generalizes the well-known multiterminal multiway) cut
problem. Two cases of metrics $\mu$ have been known for which the problem can
be solved in polynomial time: (a) $\mu$ is a modular metric whose underlying
graph $H(\mu)$ is hereditary modular and orientable (in a certain sense); and
(b) $\mu$ is a median metric. In the latter case an optimal solution can be
found by use of a cut uncrossing method. \Xcomment{We give a common
generalization for both cases by proving that the problem is in P for any
modular metric $\mu$ whose all orbit graphs are hereditary modular and
orientable. To this aim, we show the existence of a retraction of the Cartesian
product of the orbit graphs to $H(\mu)$, which enables us to elaborate an
analog of the cut uncrossing method for such metrics $\mu$.} In this paper we
generalize the idea of cut uncrossing to show the polynomial solvability for a
wider class of metrics $\mu$, which includes the median metrics as a special
case. The metric uncrossing method that we develop relies on the existence of
retractions of certain modular graphs. On the negative side, we prove that for
$\mu$ fixed, the problem is NP-hard if $\mu$ is non-modular or $H(\mu)$ is
non-orientable.
