For $k = 0,\ldots, K - 1$, $M_k$ is a subset of $\{0, \ldots, N - 1\}$, and the subsets $M_k$ are not necessarily disjoint. I want to find a permutation on $\{0, \ldots, N - 1\}$ such that the range of values of each subset is as small as possible after permuting everything. Formally speaking, let $\sigma(M) = \{\sigma(m): m \in M\}$, define$\text{range}(M, \sigma) = \max\sigma(M) - \min\sigma(M)$;then we want to find $\sigma$ that minimizes the maximum range, i.e.$\max_k\text{range}(M_k, \sigma)$.For two subsets $M_0$, $M_1$ the problem is easy: put anything in the intersection of $M_0$ and $M_1$ in the middle of the range, and for the remaining numbers put them in the bottom and top of the range for $M_0$ and $M_1$ respectively. I can imagine how one might build a greedy algorithm off of this idea.Something that might help in my specific case is that, for any two subsets $M_k$, $M_l$, the size of their intersection (if any) is much smaller than the size of the set in question, i.e. $|M_k \cap M_l| \ll \min\{|M_k|, |M_l|\}$.I'm not very knowledgeable in CS, so I imagine that this is a well-known problem; what is it called? I'm guessing it's NP-complete in general. What might be some sensible heuristics?
permuting points for range compression between subsets
algorithms;permutations