{"id":"arxiv/2609.32558","url":"https://arxiv.org/abs/2609.32558","tags":["math.OC"],"score":0,"title":"Smooth or Separable? Sparse Block Acceleration for Entropy-Regularized Linear Programs","domain":"math.OC","source":"arxiv","authors":["Irina Podlipnova","Maxim Mashtaler","Artem Agafonov","Yuriy Dorn","Alexander Gasnikov"],"reviews":0,"subject":"math.OC","summary":"We study entropy-regularized linear programs with sparse affine constraints and compare two exact dual representations induced by whether a redundant normalization constraint is retained or eliminated. Eliminating it yields a partially separable sum-exp dual with sparse affine factors but unbounded curvature. Our main result is an accelerated randomized block method whose acceleration preserves sparse data-access cost. The key ingredient is a global entropy-specific Hessian--gap bound that remains valid for signed constraint matrices, admits computable block-overlap refinements, and provides…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{}}