Skip to main content
1 of 5
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 between two permutations in $\mathfrak S_n$ where a transposition at position $i$ has cost given by weight $w_i$. 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