Recall that \(\)  is NP hard to solve in general, as for QAPs.
In particular, even though the above algorithm converges to a stationary plan [1]}, it is not necessarily the optimal one, one cannot prove its optimality, and it depends on the initialization.
Thus in [2]} several more computationally efficient lower bounds are proposed.
As proved in [3]}, these bounds are not tight, i.e. they might output a score strictly smaller than \((,)\) .
Some of them were also motivated for shape registration as computationally amenable ways of representing and comparing mm-spaces.
For instance an mm-space \(=(,d_,)\)  can be summarized using the global histogram of distances \((d_)_\sharp (\otimes )\)  [4]}, or a distribution of local distance histograms \(x\mapsto (d_(x,\cdot )_\sharp )\)  [5]}.
Those representations being distributions in \((_+)\)  or \(((_+))\) , they can be compared using OT distances.
The optimal plan \(\pi ^\star \)  obtained via those relaxations can be used as initializations for GW, or applied in place of GW in applications.
For instance the local histograms of distances representation was applied in [6]}.
