{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:38:35Z","timestamp":1770896315093,"version":"3.50.1"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,9,2]],"date-time":"2016-09-02T00:00:00Z","timestamp":1472774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"National Science Centre of Poland","doi-asserted-by":"crossref","award":["UMO-2013\/09\/B\/ST6\/03136"],"award-info":[{"award-number":["UMO-2013\/09\/B\/ST6\/03136"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,9,2]]},"abstract":"\n We study the complexity of the C\n hannel<\/jats:sc>\n A\n ssignment<\/jats:sc>\n problem. An open problem asks whether C\n hannel<\/jats:sc>\n A\n ssignment<\/jats:sc>\n admits an\n O<\/jats:italic>\n (\n \n c\n n<\/jats:sup>\n <\/jats:italic>\n ) (times a polynomial in the bit size) time algorithm, where\n n<\/jats:italic>\n is a number of the vertices, for a constant\n c<\/jats:italic>\n independent of the weights on the edges. We answer this question in the negative. Indeed, we show that in the standard Word RAM model, there is no 2\n \n o<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n )\n <\/jats:sup>\n (times a polynomial in the bit size) time algorithm solving C\n hannel<\/jats:sc>\n A\n ssignment<\/jats:sc>\n unless the exponential time hypothesis fails. Note that the currently best known algorithm works in time\n O<\/jats:italic>\n *(\n n<\/jats:italic>\n !) = 2\n \n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n )\n <\/jats:sup>\n , so our lower bound is tight (where the\n O<\/jats:italic>\n *() notation suppresses polynomial factors).\n <\/jats:p>","DOI":"10.1145\/2876505","type":"journal-article","created":{"date-parts":[[2016,9,2]],"date-time":"2016-09-02T14:33:50Z","timestamp":1472826830000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Lower Bound for the Channel Assignment Problem"],"prefix":"10.1145","volume":"12","author":[{"given":"Arkadiusz","family":"Soca\u0142a","sequence":"first","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.05.008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627892"},{"key":"e_1_2_1_4_1","first-page":"40","article-title":"Exponential algorithms: Algorithms and complexity beyond polynomial time (Dagstuhl seminar 13331)","volume":"3","author":"Husfeldt Thore","year":"2013","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_6_1","volume-title":"Algorithm Theory\u2014SWAT","author":"Kowalik \u0141ukasz","year":"2014"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.020"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133097"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133096"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00821-X"},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Computer Science","volume-title":"Parameterized and Exact Computation","author":"Traxler Patrick"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2876505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2876505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:10Z","timestamp":1750221550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2876505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,2]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,2]]}},"alternative-id":["10.1145\/2876505"],"URL":"https:\/\/doi.org\/10.1145\/2876505","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,2]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}