Tight lower bound for the channel assignment problem

DOI10.1137/1.9781611973730.45zbMATH Open1371.68217arXiv1407.7162OpenAlexW4236979639MaRDI QIDQ5363091FDOQ5363091

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)

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.

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

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

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)

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
• Approximation Algorithms for Minimum Span Channel Assignment Problems
• An exact algorithm for the channel assignment problem
• On the span in channel assignment problems: Bounds, computing and counting
• Channel assignment via fast zeta transform
• Lower Bounds from Tile Covers for the Channel Assignment Problem
• A doubly cyclic 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)