Randomized oblivious integral routing for minimizing power cost

Given an undirected network G(V, E) and a set of traffic requests R, the minimum power-cost routing problem requires that each R_k ∈ R be routed along a single path to minimize ∑_e∈E(l_e)^α, where l_e is the traffic load on edge e and α is a constant greater than 1. Typically, α ∈ (1, 3]. This problem is important in optimizing the energy consumption of networks. To address this problem, we propose a randomized oblivious routing algorithm. An oblivious routing algorithm makes decisions independently of the current traffic in the network. This feature enables the efficient implementation of our algorithm in a distributed manner, which is desirable for large-scale high-capacity networks. An important feature of our work is that our algorithm can satisfy the integral constraint, which requires that each traffic request R_k should follow a single path. We prove that, given this constraint, no randomized oblivious routing algorithm can guarantee a competitive ratio bounded by o(|E|α-1/α+1). By contrast, our approach provides a competitive ratio of O(|E|α-1/α+1 log2α/α+1 |V| · log^α-1 D), where D is the maximum demand of traffic requests. Furthermore, our results also hold for a more general case where the objective is to minimize ∑_e(l_e)^p, where p ≥ 1 is an arbitrary unknown parameter with a given upper bound α > 1. The theoretical results established in proving these bounds can be further generalized to a framework of designing and analyzing oblivious integral routing algorithms, which is significant for research on minimizing ∑_e(l_e)^α in specific scenarios with simplified problem settings. For instance, we prove that this framework can generate an oblivious integral routing algorithm whose competitive ratio can be bounded by O(log^α |V| · log^α-1 D) and O(log^3α |V| ⋅ log^α-1 D) on expanders and hypercubes, respectively.