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.

Improve this question
$\endgroup$
3
  • $\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$
    – Turbo
    Commented Mar 17, 2016 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
    Commented Mar 17, 2016 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
    Commented Jan 12, 2017 at 11:50

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .