I have the following combinatorial optimisation problem of which I think someone has probably solved it before. Has someone come across this problem before, maybe in a different setting than in the one I present it here (permutations, strings, trees, ...)?

Let $S$ be a discrete, finite set. Let $S_1, S_2, \ldots, S_k$ be subsets of $S$. Consider a linear order $R$ on $S$. We say $R$ represents $S_i$ if the elements of $S_i$ appear consecutively in $R$.

Given $S$ and $S_1, \ldots, S_k$, find a linear order $R$ of $S$ that maximises the number of subsets $S_i$ it represents.

I can solve the problem when $R$ can represent all subsets (with PQ-trees).


Let $S = \{1, 2, 3, 4, 5\}$ and $S_1 = \{1, 2, 3\}$, $S_2 = \{3, 5\}$, $S_3 = \{2, 4\}$, $S_4 = \{1, 5\}$.

For $R = (2, 1, 3, 5, 4)$, we have that $S_1$ and $S_2$ are consecuitive in $R$ but $S_3$ and $S_4$ are not.

For $R' = (4, 2, 1, 3, 5)$, we have that $S_1$, $S_2$, and $S_3$ are consecuitive in $R'$ but $S_4$ is not. Note that we can actually not do better than $R'$, which is good for three of the four subsets.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.