Value Functions of Separable Convex Integer Programs are Periodically Convex
We consider the periodic behavior of value functions $b\mapsto\min\{f(x)\ \vert\ Ax=b,\,x\in\mathbb Z_{\ge0}^n\}$ of integer programs. We show that there exists a positive integer $M$ depending only on the constraint matrix $A\in\mathbb Z^{m\times n}$ so that the value function is convex extensible on any subdomain of the form $r+M\mathbb Z^m$ for any $r\in\mathbb Z^m$ and any separable convex objective function $f$. With this, we extend the known periodic convexity of such functions for linear objective functions $f$, as established by Eisenbrand and Rothvoss (SODA 26), to the broader class…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.30330
curl -X POST /api/v1/records/arxiv/2606.30330/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.30330/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'