3

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 ...


Only top voted, non community-wiki answers of a minimum length are eligible