Half-duplex routing is NP-hard

Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Daniela Tuninetti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Routing is a widespread approach to transfer information from a source node to a destination node in many deployed wireless ad-hoc networks. Today's implemented routing algorithms seek to efficiently find the path/route with the largest Full-Duplex (FD) capacity, which is given by the minimum among the point-To-point link capacities in the path. Such an approach may be suboptimal if then the nodes in the selected path are operated in Half-Duplex (HD) mode. Recently, the capacity (up to a constant gap that only depends on the number of nodes in the path) of an HD line network (i.e., a path) has been shown to be equal to half of the minimum of the harmonic means of the capacities of two consecutive links in the path. This paper asks the question of whether it is possible to design a polynomial-Time algorithm that efficiently finds the path with the largest HD capacity in a relay network. The problem of finding such a path is shown to be NP-hard in general. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-Time algorithm can indeed be designed.

Original languageEnglish (US)
Title of host publication55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages89-96
Number of pages8
ISBN (Electronic)9781538632666
DOIs
StatePublished - Jul 1 2017
Externally publishedYes
Event55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 - Monticello, United States
Duration: Oct 3 2017Oct 6 2017

Publication series

Name55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Volume2018-January

Other

Other55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
CountryUnited States
CityMonticello
Period10/3/1710/6/17

Fingerprint Dive into the research topics of 'Half-duplex routing is NP-hard'. Together they form a unique fingerprint.

  • Cite this

    Ezzeldin, Y. H., Cardone, M., Fragouli, C., & Tuninetti, D. (2017). Half-duplex routing is NP-hard. In 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 (pp. 89-96). (55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2017.8262723