Answers are grounded in this paper and cite their sources.
In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an m-edge graph $G = (V, E)$ that is a Φ-expander, i.e. where ∂ S ≥ Φ · vol(S) for every S ⊆ V, vol(S) ≤ vol(V)/2. Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for ∞ oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing. Our main result proves that the electrical routing is an O(Φ⁻¹ log m)-competitive oblivious routing in the ₁- and _∞-norms. We further observe that the oblivious routing is O(log² m)-competitive in the ₂-norm and, in fact, O(log m)-competitive if ₂-localization is O(log m) which is widely believed. Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every p ∈ [2, ∞] and q given by $1/p + 1/q = 1$. Assuming ₂-localization in O(log m), we obtain that in ₚ and q, the electrical oblivious routing is O(Φ-(1-2/p)log m) competitive. Using the currently known result for ₂-localization, this ratio deteriorates by at most a sublogarithmic factor for every p, q ≠ 2. We complement our upper bounds with lower bounds that show that the electrical routing for any such p and q is Ω(Φ-(1-2/p)log m)-competitive. This renders our results in ₁ and ∞ unconditionally tight up to constants, and the result in any ₚ- and q-norm to be tight in case of ₂-localization in O(log m).
No takes yet. Share an insight, caveat, or question.
Florescu et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: