Online oblivious routing

ABSTRACT

We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic or demand between each pair, with the goal of minimizing the maximum congestion on any edge in the graph. In the online version of the problem, we consider a "repeated game" setting, in which the algorithm is allowed to choose a new routing each night, but is still oblivious to the demands that will occur the next day. The cost of the algorithm at every time step is its competitive ratio, or the ratio of its congestion to the minimum possible congestion for the demands at that time step.We present an algorithm that is (1+ε) competitive with respect to the best algorithm that uses a single routing for the entire sequence of days (known as the optimal static routing). Our result is a strengthening of the recent result of Azar et al [4], who gave a polynomial time algorithm to find an oblivious routing with the best possible competitive ratio, in that our algorithm achieves a competitive ratio arbitrarily to close to that of Azar et al [4], while at the same time performing nearly as well as the optimal static routing for the given sequence of demands. Our work was done independently, but subsequent to that of Azar et al [4].

REFERENCES

• 1: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 2: Peter Auer , Nicolò Cesa-Bianchi , Yoav Freund , Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, v.32 n.1, p.48-77, 2003 [doi>10.1137/S0097539701398375]
• 3: B. Awerbuch and Y. Azar. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In Foundations of Computer Science, pages 240--249, 1994.
• 4: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 5: D. Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6:1--8, 1956.
• 6: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• 7: Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
• 8: Nicoló Cesa-Bianchi, Analysis of two gradient-based algorithms for on-line regression, Journal of Computer and System Sciences, v.59 n.3, p.392-411, Dec. 1999 [doi>10.1006/jcss.1999.1635]
• 9: Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79--103, 1999.
• 10: J. Hannan. Approximation to Bayes risk in repeated play. In M. Dresher, A. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97--139. Princeton University Press, 1957.
• 11: C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97453]
• 12: A. Kalai and S. Vempala. Geometric algorithms for online optimization. Technical Report MIT-LCS-TR-861, MIT Laboratory for Computer Science, 2002.
• 13: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 14: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 15: L. Lovász. Semidefinite programs and combinatorial optimization (lecture notes). http:/research.microsoft.com/users/lovasz/semidef.ps.
• 16: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 17: Satinder P. Singh , Michael J. Kearns , Yishay Mansour, Nash Convergence of Gradient Dynamics in General-Sum Games, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.541-548, June 30-July 03, 2000
• 18: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 19: M. Warmuth and C. Gentile. Proving relative loss bounds for on-line learning algorithms using bregman divergences. In Tutorial at Computational Learning Theory (COLT), 2000.
• 20: Jyrki Kivinen , Manfred K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors, Information and Computation, v.132 n.1, p.1-63, Jan. 10, 1997 [doi>10.1006/inco.1996.2612]
• 21: M. Zinkevich. Online convex programming. Manuscript, in submission, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
competitive analysis, congestion, gradient descent, networks, oblivious routing, online algorithms