Network Coding Gaps for Completion Times of Multiple Unicasts
METADATA ONLY
Loading...
Author / Producer
Date
2020
Publication Type
Conference Paper
ETH Bibliography
no
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any lp norm of completion times.
Permanent link
Publication status
published
External links
Editor
Book title
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Journal / series
Volume
Pages / Article No.
494 - 505
Publisher
IEEE
Event
61st Annual Symposium on Foundations of Computer Science (FOCS 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Network coding; Coding gap; Multiple unicast; Nunicast; Completion time
Organisational unit
08730 - Gruppe Häupler / Group Häupler
Notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.