{"id":"arxiv/2611.15748","url":"https://arxiv.org/abs/2611.15748","tags":["math.OC","cs.DS"],"score":0,"title":"Minimizing Monotone Norms in Fractional Load Balancing","domain":"math.OC","source":"arxiv","authors":["Daniel Blankenburg","Antonia Ellerbrock","Thomas Kesselheim","Jens Vygen"],"reviews":0,"subject":"math.OC","summary":"We devise a fully polynomial time approximation scheme for minimizing a monotone norm $\\left\\lVert\\cdot\\right\\rVert$ over a convex set $X\\subseteq \\mathbb{R}^d_{\\geq 0}$. We study the multi-customer setting, where $X=\\sum_{i=1}^n X_i$ and the solution set $X_i\\subseteq \\mathbb{R}^d_{\\geq 0}$ is given by a linear minimization oracle for each customer $i$. Our algorithm computes, for any given $\\varepsilon>0$, a $(1+\\varepsilon)$-approximate solution. With high probability, it uses $\\tilde{\\mathcal{O}}\\left( \\varepsilon^{-2}(n+d) \\right)$ single-customer linear minimization oracle calls and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}