Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks

Yahya H. Ezzeldin; Martina Cardone; Christina Fragouli; Giuseppe Caire

doi:10.1109/ISIT.2019.8849671

Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks

Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Giuseppe Caire

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.

Original language	English (US)
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	460-464
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849671
State	Published - Jul 2019
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: Jul 7 2019 → Jul 12 2019

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (Print)	2157-8095

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	7/7/19 → 7/12/19

Bibliographical note

Funding Information:
Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. 1Constant gap refers to a quantity that is independent of the channel coefficients and operating SNR, and solely depends on the number of nodes.

Funding Information:
Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554.

Publisher Copyright:
© 2019 IEEE.

Access

10.1109/ISIT.2019.8849671

OpenUrl availability

Full text

Cite this

Ezzeldin, Y. H., Cardone, M., Fragouli, C., & Caire, G. (2019). Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 460-464). Article 8849671 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849671

Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks. / Ezzeldin, Yahya H.; Cardone, Martina; Fragouli, Christina et al.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 460-464 8849671 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ezzeldin, YH, Cardone, M, Fragouli, C & Caire, G 2019, Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849671, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 460-464, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/7/19. https://doi.org/10.1109/ISIT.2019.8849671

Ezzeldin YH, Cardone M, Fragouli C, Caire G. Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 460-464. 8849671. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT.2019.8849671

Ezzeldin, Yahya H. ; Cardone, Martina ; Fragouli, Christina et al. / Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks. 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 460-464 (IEEE International Symposium on Information Theory - Proceedings).

@inproceedings{9b3eba2bbd2c4240b6b538f83519c81d,

title = "Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks",

abstract = "This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point {"}beams{"} at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.",

author = "Ezzeldin, {Yahya H.} and Martina Cardone and Christina Fragouli and Giuseppe Caire",

note = "Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. 1Constant gap refers to a quantity that is independent of the channel coefficients and operating SNR, and solely depends on the number of nodes. Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/ISIT.2019.8849671",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "460--464",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

TY - GEN

T1 - Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks

AU - Ezzeldin, Yahya H.

AU - Cardone, Martina

AU - Fragouli, Christina

AU - Caire, Giuseppe

N1 - Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. 1Constant gap refers to a quantity that is independent of the channel coefficients and operating SNR, and solely depends on the number of nodes. Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. Publisher Copyright: © 2019 IEEE.

PY - 2019/7

Y1 - 2019/7

N2 - This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.

AB - This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.

UR - http://www.scopus.com/inward/record.url?scp=85073164760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073164760&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849671

DO - 10.1109/ISIT.2019.8849671

M3 - Conference contribution

AN - SCOPUS:85073164760

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 460

EP - 464

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Polynomial-time Capacity Calculation and Scheduling for Half-Duplex 1-2-1 Networks

Abstract

Publication series

Conference

Bibliographical note

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this