Let $(M,d)$ be a metric space. Consider two sequences $a = (a_i)_{i=1}^n$, $b = (b_i)_{i=1}^m$, $n, m \in \mathbb{N}$ with elements in $M$. For two sequences $[n],[m]$, call $$\Gamma([n], [m]) = \big\{E \subseteq [n] \times [m]\mid \forall i < j, k>l: \neg ((i,k) \in E \wedge (j, l) \in E)\big\}$$ the set of weakly increasing matchings (that's a title I made up for them).

Define a function $\tilde d \colon M^\mathbb N \times M^\mathbb N \to \mathbb R^+$, $$ \widetilde d(a, b) = \min_{E \in \Gamma ([n],[m])} \sum_{i, j \in E} d(a_i, b_{j}). $$ This should define a metric, which I'm tempted to call string matching distance (which seems to be, after a brief google, already taken by the edit distance, which is different). Questions:

• Does this metric have a name?
• For which classes of metrics is this metric efficiently computable/approximable?

Let $(M,d)$ be a metric space. Consider two sequences $a = (a_i)_{i=1}^n$, $b = (b_i)_{i=1}^m$, $n, m \in \mathbb{N}$ with elements in $M$. For two sequences $[n],[m]$, call $$\Gamma([n], [m]) = \big\{E \subseteq [n] \times [m]\mid \forall i < j, k>l: \neg ((i,k) \in E \wedge (j, l) \in E) \wedge \pi_1(E) = [n] \wedge \pi_2(E) = [m]\big\}$$ the set of weakly increasing matchings (that's a title I made up for them).

Define a function $\tilde d \colon M^\mathbb N \times M^\mathbb N \to \mathbb R^+$, $$ \widetilde d(a, b) = \min_{E \in \Gamma ([n],[m])} \sum_{i, j \in E} d(a_i, b_{j}). $$ This should define a metric, which I'm tempted to call string matching distance (which seems to be, after a brief google, already taken by the edit distance, which is different). Questions:

• Does this metric have a name?
• For which classes of metrics is this metric efficiently computable/approximable?

Let $(M,d)$ be a metric space. Consider two sequences $a = (a_i)_{i=1}^n$, $b = (b_i)_{i=1}^m$, $n, m \in \mathbb{N}$ with elements in $M$. For two sequences $[n],[m]$, call $\Gamma([n], [m]) = \{E \subseteq [n] \times [m]| \forall i < j, k>l: \neg ((i,k) \in E \wedge (j, l) \in E)\}$ the set of weakly increasing matchings (that's a title I made up for them).

Define a function $\tilde d \colon M^\mathbb N \times M^\mathbb N \to \mathbb R^+$, $$ \widetilde d(a, b) = \min_{E \in \Gamma ([n],[m])} \sum_{i, j \in E} d(a_i, b_{j}). $$ This should define a metric, which I'm tempted to call string matching distance (which seems to be, after a brief google, already taken by the edit distance, which is different). Questions:

• Does this metric have a name?
• For which classes of metrics is this metric efficiently computable/approximable?

Let $(M,d)$ be a metric space. Consider two sequences $a = (a_i)_{i=1}^n$, $b = (b_i)_{i=1}^m$, $n, m \in \mathbb{N}$ with elements in $M$. For two sequences $[n],[m]$, call $$\Gamma([n], [m]) = \big\{E \subseteq [n] \times [m]\mid \forall i < j, k>l: \neg ((i,k) \in E \wedge (j, l) \in E)\big\}$$ the set of weakly increasing matchings (that's a title I made up for them).

Define a function $\tilde d \colon M^\mathbb N \times M^\mathbb N \to \mathbb R^+$, $$ \widetilde d(a, b) = \min_{E \in \Gamma ([n],[m])} \sum_{i, j \in E} d(a_i, b_{j}). $$ This should define a metric, which I'm tempted to call string matching distance (which seems to be, after a brief google, already taken by the edit distance, which is different). Questions:

• Does this metric have a name?
• For which classes of metrics is this metric efficiently computable/approximable?