A colorful Steinitz Lemma with application to block-structured integer programs

Oertel T, Paat J, Weismantel R (2023)

Publication Type: Journal article

Publication year: 2023

Journal

Mathematical Programming Springer Verlag (Germany)

DOI: 10.1007/s10107-023-01971-3

Abstract

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.

Authors with CRIS profile

Timm Oertel Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

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

How to cite

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