Assigning channels via the meet-in-the-middle approach

Abstract

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $\ell$-bounded Channel Assignment (when the edge weights are bounded by $\ell$) running in time $O^{\ast }((2\sqrt{\ell +1}{)}^n)$. This is the first algorithm which breaks the $(O(\ell ){)}^n$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. A major open problem asks whether Channel Assignment admits a $O(c^n)$-time algorithm, for a constant $c$ independent of $\ell$. We consider a similar question for Generalized T-Coloring, a CSP problem that generalizes \CA. We show that Generalized T-Coloring does not admit a $2^{2^{o\left(\sqrt{n}\right)}}\mathrm{poly}(r)$-time algorithm, where $r$ is the size of the instance.

SWAT 2014: 282-293

References in corpus (1)

• Channel Assignment via Fast Zeta Transform