Tight lower bound for the channel assignment problem

We study the complexity of theChannel Assignment problem. A major open problem asks whether Channel Assignment admits an O(cn)-time algorithm, for a constant c independent of the weights on the edges. We answer this question in the negative i.e. we show that there is no 2o(n logn)-time algorithm solving Channel Assignment unless the Exponential Time Hypothesis fails. Note that the currently best known algorithm works in timeO∗(n!) = 2O(n logn) so our lower bound is tight. ∗E-mail