How to Uncross Some Modular Metrics

Details How to Uncross Some Modular Metrics How to Uncross Some Modular Metrics

2000-04-13

arxiv.org/abs/math/0004090v1

Mathematics

Combinatorics

25 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

How to Uncross Some Modular Metrics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How to Uncross Some Modular Metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to Uncross Some Modular Metrics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-573739