4 papers
A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
Ian D'Ambrosio
Dynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses integral rep…
Always-Correct Succinct Dynamic Fusion Nodes Are Impossible: A Cell-Probe Lower Bound in the Small-Set, Large-Universe Regime
Ian D'Ambrosio
Kuszmaul, Liang, and Zhou (SODA 2026) ask whether succinct constant-time dynamic fusion nodes exist when the number of stored keys is polylogarithmic in the universe size. We give…
An Exact Counterexample to Affine-Like Price-of-Anarchy Shape in Quartic BPR Routing
Ian D'Ambrosio
We give an exact computer-assisted counterexample to a direct common-degree quartic extension of the affine active-network shape theorem for demand-dependent Price of Anarchy. The…
A Tight Linear Deterministic Competitive Ratio for Fully Online KV-Cache Scheduling
Ian D'Ambrosio
Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved that eve…