# Choosing $K$ “centers” from the space of permutations

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.

• @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. – T.... Mar 17 '16 at 23:25
• @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. – Tom Solberg Mar 17 '16 at 23:35
• @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.? – Abdelmalek Abdesselam Jan 12 '17 at 11:50

It contains code for determining the $k$th permutation and also discusses successive refinement of a set of permutations.