{"id":"arxiv/2607.11241","url":"https://arxiv.org/abs/2607.11241","tags":["cs.DS","math.CO"],"score":0,"title":"Bounded-Support Additive Latin Transversals","domain":"cs.DS","source":"arxiv","authors":["Antoine Deza","Yan Gerard","Yijun Ma","Sebastian Pokutta"],"reviews":0,"subject":"cs.DS","summary":"We consider the following additive Latin transversal problem. Given a multiset $A=(a_1,\\dots,a_k)$ of elements of $\\mathbb Z_m$ and a set $B\\subseteq\\mathbb Z_m$ of cardinality $k$, the task is to order $B$ as $b_1,\\dots,b_k$ so that the sums $a_i+b_i$ are pairwise distinct. When $k=m$, Hall proved that a solution exists if and only if $\\sum_{i=1}^m a_i\\equiv 0 \\pmod m$; moreover, his theorem yields a polynomial-time construction. Alon proved that a solution always exists when $m$ is prime and $k<m$, but no polynomial-time construction is known in general. Our main algorithmic contribution…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}