TY - GEN
T1 - Improved guarantees for tree cut sparsifiers
AU - Räcke, Harald
AU - Shah, Chintan
PY - 2014
Y1 - 2014
N2 - Harrelson, Hildrum and Rao [11] construct for a given graph a single tree that acts as a flow sparsifier, i.e., it can approximate multicommodity flows in G up to an O(log 2 nloglog n) factor. Many applications that use these trees do not actually require a flow sparsifier but would already work with just having a cut sparsifier. We show how to construct a cut sparsifier that is a single tree and has quality O(log 1.5 nloglog n). In addition we show a close connection of this problem to the Mincut Linear Arrangement Problem which shows that improving the guarantee to o(log 1.5 n) might be difficult.
AB - Harrelson, Hildrum and Rao [11] construct for a given graph a single tree that acts as a flow sparsifier, i.e., it can approximate multicommodity flows in G up to an O(log 2 nloglog n) factor. Many applications that use these trees do not actually require a flow sparsifier but would already work with just having a cut sparsifier. We show how to construct a cut sparsifier that is a single tree and has quality O(log 1.5 nloglog n). In addition we show a close connection of this problem to the Mincut Linear Arrangement Problem which shows that improving the guarantee to o(log 1.5 n) might be difficult.
UR - http://www.scopus.com/inward/record.url?scp=84958545515&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-44777-2_64
DO - 10.1007/978-3-662-44777-2_64
M3 - Conference contribution
AN - SCOPUS:84958545515
SN - 9783662447765
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 774
EP - 785
BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PB - Springer Verlag
T2 - 22nd Annual European Symposium on Algorithms, ESA 2014
Y2 - 8 September 2014 through 10 September 2014
ER -