Oertel T, Paat J, Weismantel R (2023)

**Publication Type:** Journal article

**Publication year:** 2023

**DOI:** 10.1007/s10107-023-01971-3

The Steinitz constant in dimension d is the smallest value c(d) such that for any norm on R-d and for any finite zero-sum sequence in the unit ball, the sequence can be permuted such that the norm of each partial sum is bounded by c(d). Grinberg and Sevastyanov prove that c(d) = d and that the bound of d is best possible for arbitrary norms; we refer to their result as the Steinitz Lemma. We present a variation of the Steinitz Lemma that permutes multiple sequences at one time. Our result, which we term a colorful Steinitz Lemma, demonstrates upper bounds that are independent of the number of sequences. Many results in the theory of integer programming are proved by permuting vectors of bounded norm; this includes proximity results, Graver basis algorithms, and dynamic programs. Due to a recent paper of Eisenbrand and Weismantel, there has been a surge of research on how the Steinitz Lemma can be used to improve integer programming results. As an application we prove a proximity result for block-structured integer programs.

University of British Columbia
Canada (CA)
Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich
Switzerland (CH)

**APA:**

Oertel, T., Paat, J., & Weismantel, R. (2023). A colorful Steinitz Lemma with application to block-structured integer programs. *Mathematical Programming*. https://dx.doi.org/10.1007/s10107-023-01971-3

**MLA:**

Oertel, Timm, Joseph Paat, and Robert Weismantel. "A colorful Steinitz Lemma with application to block-structured integer programs." *Mathematical Programming* (2023).

**BibTeX:** Download