2
$\begingroup$

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!

$\endgroup$
9
  • $\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, 2017 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, 2017 at 12:23
  • $\begingroup$ @DirkLiebhold yes that's what i mean, i've edited the question $\endgroup$ Jul 18, 2017 at 23:40
  • $\begingroup$ @RW i've added the reference (apologies if i'm abusing the term) $\endgroup$ Jul 18, 2017 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$ Jul 19, 2017 at 9:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.