Metraipolis › archive › dc_2301df22fae3
Network Speed Scaling with Competitive Ratios Independent of the Network — arXiv:2610.03848
- Source
- arXiv
- Original
- https://arxiv.org/abs/2610.03848
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T05:29:13.361Z
- SHA-256 of the archived text
dcc3643d6fdd9e0716092bab179ac13c1404324d0757838f38b905628f19a7de- Stable URL of this page
https://metraipolis.com/documento/dc_2301df22fae3
How to cite
Network Speed Scaling with Competitive Ratios Independent of the Network — arXiv:2610.03848 — arXiv, https://arxiv.org/abs/2610.03848 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2301df22fae3 (Metraipolis archive dc_2301df22fae3, sha256 dcc3643d6fdd9e0716092bab179ac13c1404324d0757838f38b905628f19a7de)
BibTeX
@misc{dc2301df22fae3,
title = {Network Speed Scaling with Competitive Ratios Independent of the Network — arXiv:2610.03848},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2610.03848},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2301df22fae3; sha256 dcc3643d6fdd9e0716092bab179ac13c1404324d0757838f38b905628f19a7de},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.03848. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In network speed scaling, jobs arrive over time at a network of servers whose speeds can be tuned, every job must be processed by the servers along one of its allowed routes, and the goal is to minimize the total flow time plus the total energy. For stochastic arrivals, the competitive ratio of Vaze and Nair depends on the network, through the lengths of the routes it uses. We show that this dependence can be removed: we give an algorithm, which routes the jobs by solving a convex program and runs every server at a fixed speed, whose competitive ratio depends only on the power functions; for $P(s)=s^2$, it is at most the golden ratio $\varphi\approx1.618$. The key idea is a lower bound on the optimal cost which, like the cost of our algorithm, is a sum over the servers of a function of each server's load, so the analysis reduces to a single server. We also show that the routing rule of Vaze and Nair can be a factor $\Omega(L)$ away from optimal, where $L$ is the length of the longest route. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.PF, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Performance (cs.PF). Pagina del lavoro: https://arxiv.org/abs/2610.03848 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T05:25:05.313Z dalla pagina https://arxiv.org/list/cs.PF/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).