← 研踪 PaperTrailarXiv:2611.13859 · v1
Online Network Design with Additive Delays and Poisson Arrivals
首次提交 2026-11-10 18:18
版本更新 2026-11-10 18:18
雷达观测 2026-11-11 11:04
摘要
We study online service systems in which requests arrive at locations in a network. A service may open a facility and connect customers, buy a subtree linking them to a root, or send a mobile server to visit them. Combining requests can save opening, network, or travel costs, but each request pays its own waiting time. The objective is the sum of these spatial costs and individual delays. We assume independent Poisson arrivals of known rates. The algorithms know how often requests occur, but observe them only upon arrival. We show that these rates suffice to make fixed spatial choices that compete with an offline optimum free to adapt to the realized input. We obtain long-run ratios of expectations below $27.249$ for facility location in finite metrics, $94.415$ for multi-root aggregation on trees, and $24.326$ for online service on trees. All three algorithms are deterministic; the multi-root algorithm also has polynomial-time preprocessing on rational inputs. The proofs connect rate-based spatial choices with lower bounds on unavoidable purchase, movement, and waiting costs. All main proofs are self-contained, and every guarantee includes the full cost of completing finite inputs.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 18:18 · 最新观测版本
Online Network Design with Additive Delays and Poisson Arrivals
We study online service systems in which requests arrive at locations in a network. A service may open a facility and connect customers, buy a subtree linking them to a root, or send a mobile server to visit them. Combining requests can save opening, network, or travel costs, but each request pays its own waiting time. The objective is the sum of these spatial costs and individual delays. We assume independent Poisson arrivals of known rates. The algorithms know how often requests occur, but observe them only upon arrival. We show that these rates suffice to make fixed spatial choices that compete with an offline optimum free to adapt to the realized input. We obtain long-run ratios of expectations below $27.249$ for facility location in finite metrics, $94.415$ for multi-root aggregation on trees, and $24.326$ for online service on trees. All three algorithms are deterministic; the multi-root algorithm also has polynomial-time preprocessing on rational inputs. The proofs connect rate-based spatial choices with lower bounds on unavoidable purchase, movement, and waiting costs. All main proofs are self-contained, and every guarantee includes the full cost of completing finite inputs.
查看此版本解读 →查看此版本原文 ↗