Tight lower bound for the channel assignment problem

DOI10.1137/1.9781611973730.45MaRDI QIDQ5363091zbMATH OpenOpenAlexFDO

Authors Arkadiusz Socała

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.7162

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We study the complexity of the Channel Assignment problem. A major open problem asks whether Channel Assignment admits an $O(c^n)$-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 $2^{o(nlogn)}$-time algorithm solving Channel Assignment unless the Exponential Time Hypothesis fails. Note that the currently best known algorithm works in time $O^{\ast }(n!)=2^{O(nlogn)}$ so our lower bound is tight.

Recommendations

• Tight lower bound for the channel assignment problem
• Assigning channels via the meet-in-the-middle approach
• Assigning channels via the meet-in-the-middle approach
• An exact algorithm for the channel assignment problem
• Channel assignment via fast zeta transform

Cited in

(16)

• On the finite transmission zero assignment problem
• Optimal channel assignment and \(L(p,1)\)-labeling
• Assigning channels via the meet-in-the-middle approach
• Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
• Channels With Cost Constraints: Strong Converse and Dispersion
• An exact algorithm for the channel assignment problem
• On the span in channel assignment problems: Bounds, computing and counting
• Approximation Algorithms for Minimum Span Channel Assignment Problems
• Channel assignment via fast zeta transform
• A doubly cyclic channel assignment problem
• Lower Bounds from Tile Covers for the Channel Assignment Problem
• The channel assignment problem for mutually adjacent sites
• A Theorem about the Channel Assignment Problem
• Assigning channels via the meet-in-the-middle approach
• On the fine-grained complexity of rainbow coloring
• Tight lower bound for the channel assignment problem

This page was built for publication: Tight lower bound for the channel assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363091)