Working on a pet project I stumbled across an (at least to me) unknown problem which I am not able to reduce to already known and well studied combinatorial problems such as Knapsack or TSP. My gut tells me this problem cannot be optimally solved efficiently unless P=NP and greedy approaches do not lead to optimal solutions.
Have you already seen this problem? Do you agree with my intuition? Are you able to reduce it to well studied problems?
Definitions
Tuple: a set of 3 letters without repetitions, where the order does not matter. For example <A, B, C> or <D, A, G>. In this context <A, B, C> is equal to <C, B, A>.
Lookup table: a table assigning to each letter a distinct position, where the positions are strictly increasing subsequent numbers. For example:
| Position | Letter |
|---|---|
| 0 | A |
| 1 | B |
| 2 | C |
| 3 | D |
| 4 | E |
| 5 | F |
Distance: the number of subsequent rows needed to cover a tuple. It describes the distance between the lower and the higher position for all the letters in the tuple for a given lookup table. Different lookup tables yield different distances.
For example using the table above, the tuple <A,C,B> has a distance of 3 while the tuple <B,D,F> has a distance of 5.
| Position | Letter | Tuple <A,C,B> | Tuple <B,D,F> |
|---|---|---|---|
| 0 | A | X | |
| 1 | B | X | X |
| 2 | C | X | - |
| 3 | D | X | |
| 4 | E | - | |
| 5 | F | X | |
| Distance | 3 | 5 |
Problem statement
Given a collection of tuples as input, find the best possible lookup table which minimises the total distance. The total distance is defined as the sum of the distance for each tuple.
Analysis
The lookup table has $N!$ possible permutations. Using brute-force it is possible to solve the problem, although not feasible for big instances.
This problem can maybe be attacked using Simulated annealing or similar techniques.
Questions
- How can this problem be approximated with a polynomial algorithm?
- Can this problem be reduced to well known problems?
Thanks everybody in advance for your help
You can solve the problem via constraint programming as follows. Rename your letters $A,B,C,\dots$ as $\{0,\dots,n-1\}$. Let integer decision variable $x_i$ represent the position of letter $i$ in the lookup table. Let $T$ be the set of triples. For $\{i_1,i_2,i_3\}\in T$, let integer decision variable $y_{i_1 i_2 i_3}$ represent the distance. The problem is to minimize $\sum_{i_1, i_2, i_3} y_{i_1 i_2 i_3}$ subject to \begin{align} &\text{ALLDIFF}(x_0,\dots,x_{n-1}) \\ y_{i_1 i_2 i_3} &\ge x_j - x_k + 1 &&\text{for all $\{i_1,i_2,i_3\}\in T$ and $j,k\in\{i_1,i_2,i_3\}$} \\ x_i &\in \{0,\dots,n-1\} &&\text{for all $i$} \end{align} For your example with $n=6$ and $T=\{\{0,1,2\},\{1,3,5\}\}$, an optimal solution is $$x_0=0,x_1=2,x_2=1,x_3=4,x_4=5,x_5=3, y_{0,1,2}=3, y_{1,3,5}=3,$$ with objective value $3+3=6$.
I used constraint programming because of ALLDIFF, but you could instead use integer linear programming, with binary decision variables $x_{ip}$ to indicate whether $x_i=p$, where $p\in \{0,\dots,n-1\}$. The constraints would then be \begin{align} \sum_p x_{ip} &= 1 &&\text{for all $i$} \\ \sum_i x_{ip} &= 1 &&\text{for all $p$} \\ y_{i_1 i_2 i_3} &\ge \sum_p p(x_{jp} - x_{kp}) + 1 &&\text{for all $\{i_1,i_2,i_3\}\in T$ and $j,k\in\{i_1,i_2,i_3\}$} \\ x_{ip} &\in \{0,1\} &&\text{for all $i$ and $p$} \end{align}
If you had pairs instead of triples, this would be the minimum linear arrangement problem, which is known to be NP-hard. Your problem is a generalization to $3$-uniform hypergraphs.