9
$\begingroup$

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations $\pi_1,\dots,\pi_K$ so as to minimize the maximum distance between any permutation $\pi\in\Pi$ and one of the selected $K$ permutations, that is, I want to solve the following optimization problem: $$\mathrm{minimize}_{\pi_1,\dots,\pi_K\in \Pi} \max_{\pi\in\Pi} \min_k d(\pi,\pi_k) $$In other words, I'm looking for a set of $K$ permutations that is as "spread out" in $\Pi$ as possible.

My question: are there any well-known metrics $d(\cdot,\cdot)$ that allow me to bound the distance above in terms of $K$? In other words, are there any statements of the form "if $K=(*)$ and metric $(**)$ is used, then it is possible to select $K$ centers such that every permutation $\pi$ is at most $(***)$ distance away from its nearest center"? Obviously, $K$ will need to be huge for this to make sense, so I'm particularly interested in the case where $K=(aN)!$ for $a$ close to $1$, for example.

$\endgroup$
  • $\begingroup$ @TomSelberg Not easy. Usually one sets a set on which $S_n$ acts and study distances on this set and this seems like permutation codes. There can be other metrics. Unless the set is structured there is literally no hope. Why this problem though? Any reasons you seek? You have added 'optimization-control' tag. $\endgroup$ – T.... Mar 17 '16 at 23:25
  • 2
    $\begingroup$ @Turbo I'm studying a problem that's distantly related to the Euclidean travelling salesman problem, where the goal is to select an optimal sequence to visit a set of points. I'm interested in determining if it's possible to find a "good solution" by enumerating a set of, say, $(0.9N)!$ permutations, and selecting the best one. $\endgroup$ – Tom Solberg Mar 17 '16 at 23:35
  • $\begingroup$ @Tom: it doesn't seem like $\Pi$ being a set of permutations plays any role in your problem. Why not just set let $\Pi$ be a finite set etc.? $\endgroup$ – Abdelmalek Abdesselam Jan 12 '17 at 11:50
1
$\begingroup$

If the "unit distance" corresponds to exactly two elements having exchanged positions, then the answer to this question may be in the line of what you are looking for.
It contains code for determining the $k$th permutation and also discusses successive refinement of a set of permutations.

More generally, you could look for Gray codes for permutations like e.g. in this paper

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.