# Tag Info

Let $\alpha \in \Sigma$ and $d_{\alpha, H}(A,B) = n - \sum1\{A(i)=B(i)=\alpha\}$. Then you can use your FFT technique to compute $d_{\alpha, H}(A, B)$ for each $\alpha \in \Sigma$. It will take $O(n \cdot \log(n) \cdot |\Sigma|)$ time. So you will have an $|\Sigma| \times n$ table, where you should find a column with a minimum sum, which can be done in $O(|\... 1 Start with an integer program for your problem. For each$i$, there is a variable$x_i \in \{0,1\}$which represents which way the$i$'th message is routed. You can express the number of messages going through an edge$e$as some linear combination$y_e$of the$x_i$'s. Your goal is to minimize$\max(y_e)$. Equivalently, you want to minimize$m\$ under the ...