ABSTRACT
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (with respect to edge congestion) for any undirected graph. However, there are directed networks for which the competitive ratio is in Ω(√n).To cope with this inherent hardness in general directed networks, the concept of oblivious routing with demands chosen randomly from a known demand distribution was introduced recently. Under this new model, O(log2 n)-competitiveness with high probability is possible in general directed graphs.However, it remained an open problem whether or not the competitive ratio, under this new model, could also be significantly improved in undirected graphs. In this paper, we rule out this possibility by providing a lower bound of Ω(log n/log log n) for the multicommodity case and Ω(√logn) for the single-sink case for oblivious routing in a random demand model.We also introduce a natural candidate model for evaluating the throughput of an oblivious routing scheme which subsumes all suggested models for the throughput of oblivious routing considered so far. In this general model, we first prove a lower bound Ω(log n/log log n) for the competitive ratio of any oblivious routing scheme. Interestingly, the graphs that we consider for the lower bound in this case are expanders, for which we also obtain a lower bound Ω(log n/log log n) on the competitive ratio of congestion based oblivious routing with adversarial demands.
Index Terms
- New lower bounds for oblivious routing in undirected graphs
Recommendations
Oblivious routing in directed graphs with random demands
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingOblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. More precisely, Räcke showed that there is an oblivious routing algorithm with polylogarithmic ...
Oblivious routing on node-capacitated and directed graphs
Oblivious routing algorithms for general undirected networks were introduced by Räcke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or ...
Super-linear time-space tradeoff lower bounds for randomized computation
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceWe prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...
Comments