## 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 | |

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.