How to Uncross Some Modular Metrics
| dc.creator | Karzanov, Alexander V. | |
| dc.date | 2000-04-13 | |
| dc.date.accessioned | 2026-07-07T04:34:45Z | |
| dc.date.available | 2026-07-07T04:34:45Z | |
| dc.description | Let $μ$ 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 $μ$ 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 $μ$ have been known for which the problem can be solved in polynomial time: (a) $μ$ is a modular metric whose underlying graph $H(μ)$ is hereditary modular and orientable (in a certain sense); and (b) $μ$ 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 $μ$ 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(μ)$, which enables us to elaborate an analog of the cut uncrossing method for such metrics $μ$.} In this paper we generalize the idea of cut uncrossing to show the polynomial solvability for a wider class of metrics $μ$, 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 $μ$ fixed, the problem is NP-hard if $μ$ is non-modular or $H(μ)$ is non-orientable. | |
| dc.description | 25 pages | |
| dc.identifier | https://arxiv.org/abs/math/0004090 | |
| dc.identifier | http://arxiv.org/abs/math/0004090 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/59023 | |
| dc.subject | Combinatorics | |
| dc.title | How to Uncross Some Modular Metrics | |
| dc.type | text |