TY - GEN
T1 - Coding in undirected graphs is either very helpful or not helpful at all
AU - Braverman, Mark
AU - Garg, Sumegha
AU - Schvartzman, Ariel
N1 - Funding Information:
Research supported in part by an NSF Awards, DMS-1128155, CCF-1525342, and CCF-1149888
Funding Information:
∗ Research supported in part by an NSF Awards, DMS-1128155, CCF-1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured in [11] that the answer is 'no'. In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs that exhibits a (1 + ϵ) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G0 whose gap is log(|G'|)c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G'|), which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-Amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G'|)c from any initial gap.
AB - While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured in [11] that the answer is 'no'. In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs that exhibits a (1 + ϵ) gap between its MCF rate and its network coding rate can be used to construct a family of graphs G0 whose gap is log(|G'|)c for some constant c < 1. The resulting gap is close to the best currently known upper bound, log(|G'|), which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-Amplifying graph tensor product that, given two graphs G1,G2 with small gaps, creates another graph G with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of log(|G'|)c from any initial gap.
KW - Gap Amplification
KW - Multicommodity flows
KW - Network coding
UR - http://www.scopus.com/inward/record.url?scp=85038593618&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038593618&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2017.18
DO - 10.4230/LIPIcs.ITCS.2017.18
M3 - Conference contribution
AN - SCOPUS:85038593618
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
A2 - Papadimitriou, Christos H.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Y2 - 9 January 2017 through 11 January 2017
ER -