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!

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

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .