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

$$(n-1)w_1 + (n-2) w_2 + \cdots + w_{n-1}$$

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

Apologies if this is a very obvious question!

  • $\begingroup$ Can you give a formal definition of the term "weighted earth-mover's distance between permutations". And what is a "transposition at position $i$?" Do you mean the transposition $(i,i+1)$? $\endgroup$ – Dirk Jul 18 '17 at 9:19
  • $\begingroup$ Are you talking just about just the usual graph metric on the Cayley graph of the symmetric group with respect to the generating set which consists of permutations with weighted lengths? It has nothing to do with any "earth-moving" (which only arises when one talks about distances between measures). $\endgroup$ – R W Jul 18 '17 at 12:23
  • $\begingroup$ @DirkLiebhold yes that's what i mean, i've edited the question $\endgroup$ – Max Flander Jul 18 '17 at 23:40
  • $\begingroup$ @RW i've added the reference (apologies if i'm abusing the term) $\endgroup$ – Max Flander Jul 18 '17 at 23:44
  • $\begingroup$ I don't think your formula for the distance between the identity and the longest permutation is correct. $w_n$ shouldn't appear at all, and, unless I'm misunderstanding, $w_1$ would appear twice, once for position 1, and once for position $n$. $\endgroup$ – Hugh Thomas Jul 19 '17 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.