2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This sounds similar to the NP-complete problem known as minimum bandwidth. $\endgroup$ – Yuval Filmus Feb 5 '17 at 21:38
  • $\begingroup$ @YuvalFilmus I was thinking something along those lines too. Maybe define a graph $G$ on $\{0, \ldots, N - 1\}$ such that solving the minimum bandwidth problem for $G$ is equivalent to the original problem, then I can just use Cuthill-McKee. $\endgroup$ – korrok Feb 6 '17 at 1:55

Your Answer

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

Browse other questions tagged or ask your own question.