Almost optimal permutation routing on hypercubes

DOI10.1145/380752.380848zbMath1323.68019MaRDI QIDQ5176011

Berthold Vöcking

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380848

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms

Related Items

Optimal permutation routing for low-dimensional hypercubes, Survey on Oblivious Routing Strategies

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)