Skip to main content
3 of 5
added 1 character in body
Max Flander
  • 821
  • 6
  • 12

What is the maximum weighted earth-movers distance between two permutations?

What is the maximum weighted earth-mover's distance (as defined in Sun et. al. 2010) between two permutations in $\mathfrak S_n$ where the transposition $(i, i+1)$ has cost given by weight $w_i$. In other words

enter image description here

Is it

$$w_1 + 2w_2 + 3w_3 + \cdots + 3w_{n-2} + 2w_{n-1} + w_n$$

for the permuations $(12\cdots n)$ and $(n(n-1)\cdots 1)$?

Apologies if this is a very obvious question!

Max Flander
  • 821
  • 6
  • 12