% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@article{faucris.304475623,
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.},
author = {Oertel, Timm and Paat, Joseph and Weismantel, Robert},
doi = {10.1007/s10107-023-01971-3},
faupublication = {yes},
journal = {Mathematical Programming},
note = {CRIS-Team WoS Importer:2023-06-02},
peerreviewed = {Yes},
title = {{A} colorful {Steinitz} {Lemma} with application to block-structured integer programs},
year = {2023}
}
@article{faucris.263690904,
abstract = {We introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are "best possible" in a certain sense. Motivated by this, we establish structural results about this concept and provide efficient algorithms for computing these points. Our main motivation is to understand the complexity of oracle-based convex mixed-integer optimization.},
author = {Basu, Amitabh and Oertel, Timm},
doi = {10.1137/16M1092908},
faupublication = {no},
journal = {SIAM Journal on Optimization},
keywords = {Centerpoints; Convex and discrete geometry; Convex mixed-integer optimization},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {866-889},
peerreviewed = {Yes},
title = {{Centerpoints}: {A} link between optimization and convex geometry},
volume = {27},
year = {2017}
}
@article{faucris.317920992,
abstract = {Given a rational pointed n-dimensional cone C, we study the integer Carathéodory rank CR(C) and its asymptotic form CRa(C), where we consider “most” integer vectors in the cone. The main result significantly improves the previously known upper bound for CRa(C). We also study bounds on CR(C) in terms of Δ, the maximal absolute n×n minor of the matrix given in an integral polyhedral representation of C. If Δ∈{1,2}, we show that CR(C)=n, and prove upper bounds for simplicial cones, improving the best known upper bound on CR(C) for Δ≤n.

n-dimensional cone C, we study the integer Carathéodory rank CR(C) and its asymptotic form CR^{a}(C), where we consider “most” integer vectors in the cone. The
main result significantly improves the previously known upper bound for CR^{a}(C). We also study bounds on CR(C) in terms of Δ, the maximal absolute n×n minor of the matrix given in an integral
polyhedral representation of C. If Δ∈{1,2}, we show that CR(C)=n, and prove upper bounds for simplicial cones,
improving the best known upper bound on CR(C) for Δ

t≥0 that have the smallest number of nonzero entries. Our tools are algebraic and number theoretic in nature and include Siegel’s lemma, generating functions, and commutative algebra. These results have some interesting consequences in discrete optimization.},
author = {Aliev, Iskander and De Loera, Jesus A. and Oertel, Timm and O'Neill, Christopher},
doi = {10.1137/16M1083876},
faupublication = {no},
journal = {SIAM Journal on Applied Algebra and Geometry},
keywords = {Discrete geometry; Integer programming; Optimization},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {239-253},
peerreviewed = {Yes},
title = {{Sparse} solutions of linear diophantine equations},
volume = {1},
year = {2017}
}
@article{faucris.263689655,
abstract = {We consider the asymptotic distribution of the integer program (IP) sparsity function, which measures the minimal support of optimal IP solutions, and the IP to linear program (LP) distance function, which measures the distance between optimal IP and LP solutions. We create a framework for studying the asymptotic distributions of general functions related to integer optimization. There has been a significant amount of research focused on the extreme values that these functions can attain. However, less is known about their typical values. Each of these functions is defined for a fixed constraint matrix and objective vector while the right-hand sides are treated as input. We show that the typical values of these functions are smaller than the known worst case bounds by providing a spectrum of probability-like results that govern their overall asymptotic distributions.},
author = {Oertel, Timm and Paat, Joseph and Weismantel, Robert},
doi = {10.1137/19M1275954},
faupublication = {no},
journal = {SIAM Journal on Applied Algebra and Geometry},
keywords = {Distance; Integer optimization; Sparsity},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {422-440},
peerreviewed = {Yes},
title = {{The} distributions of functions related to parametric integer optimization},
volume = {4},
year = {2020}
}
@article{faucris.263691411,
abstract = {The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by A∈Z^{m×n} and find an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in A and m are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of A lie between 1 and a constant.},
author = {Artmann, S. and Eisenbrand, F. and Glanzer, C. and Oertel, Timm and Vempala, S. and Weismantel, R.},
doi = {10.1016/j.orl.2016.07.004},
faupublication = {no},
journal = {Operations Research Letters},
keywords = {Integer programming; Linear programming; Restricted determinants},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {635-639},
peerreviewed = {Yes},
title = {{A} note on non-degenerate integer programs with small sub-determinants},
volume = {44},
year = {2016}
}
@article{faucris.263692171,
abstract = {Zn, where f is a nonlinear function, P â' Rn is a polyhedron, and W â ZdÃn. As a consequence of our representation theorem, we obtain a general efficient transformation from the latter class of problems to integer linear programming. Our bounds depend polynomially on various important parameters of the input data leading, among others, to first polynomial time algorithms for several classes of nonlinear optimization problems.},
author = {Adjiashvili, David and Oertel, Timm and Weismantel, Robert},
doi = {10.1137/14M0973694},
faupublication = {no},
journal = {SIAM Journal on Discrete Mathematics},
keywords = {Frobenius problem; Integer optimization; Nonlinear optimization; Polyhedron},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {1287-1302},
peerreviewed = {Yes},
title = {{A} polyhedral frobenius theorem with applications to integer optimization},
volume = {29},
year = {2015}
}
@article{faucris.263689403,
abstract = {We give an optimal upper bound for the ℓ∞-distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point. In a randomised setting, we show that the upper bound can be significantly improved on average. As a corollary, we obtain an optimal upper bound for the additive integrality gap of integer knapsack problems and show that the integrality gap of a “typical” knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario. We also prove that, in a generic case, the integer programming gap admits a natural optimal lower bound.},
author = {Aliev, Iskander and Henk, Martin and Oertel, Timm},
doi = {10.1007/s10107-019-01392-1},
faupublication = {no},
journal = {Mathematical Programming},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {175-198},
peerreviewed = {unknown},
title = {{Distances} to lattice points in knapsack polyhedra},
volume = {182},
year = {2020}
}
@article{faucris.263691663,
abstract = {We extend in two ways the standard Karush–Kuhn–Tucker optimality conditions to problems with a convex objective, convex functional constraints, and the extra requirement that some of the variables must be integral. While the standard Karush–Kuhn–Tucker conditions involve separating hyperplanes, our extension is based on mixed-integer-free polyhedra. Our optimality conditions allow us to define an exact dual of our original mixed-integer convex problem.},
author = {Baes, Michel and Oertel, Timm and Weismantel, Robert},
doi = {10.1007/s10107-015-0917-y},
faupublication = {no},
journal = {Mathematical Programming},
keywords = {90C11; 90C46},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {547-564},
peerreviewed = {Yes},
title = {{Duality} for mixed-integer convex minimization},
volume = {158},
year = {2016}
}
@article{faucris.263692673,
abstract = {Minimizing a convex function over the integral points of a bounded convex set is polynomial in fixed dimension (Grötschel et al., 1988). We provide an alternative, short, and geometrically motivated proof of this result. In particular, we present an oracle-polynomial algorithm based on a mixed integer linear optimization oracle. © 2014 Elsevier B.V. All rights reserved.},
author = {Oertel, Timm and Wagner, Christian and Weismantel, Robert},
doi = {10.1016/j.orl.2014.07.005},
faupublication = {no},
journal = {Operations Research Letters},
keywords = {Convex minimization; Integer optimization; Polynomial algorithm},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {424-428},
peerreviewed = {Yes},
title = {{Integer} convex minimization by mixed integer linear optimization},
volume = {42},
year = {2014}
}
@inproceedings{faucris.263691155,
abstract = {We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a “typical” knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.},
author = {Aliev, Iskander and Henk, Martin and Oertel, Timm},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
date = {2017-06-26/2017-06-28},
doi = {10.1007/978-3-319-59250-3{\_}3},
editor = {Friedrich Eisenbrand, Jochen Koenemann},
faupublication = {no},
isbn = {9783319592497},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {25-38},
peerreviewed = {unknown},
publisher = {Springer Verlag},
title = {{Integrality} gaps of integer knapsack problems},
venue = {Waterloo, ON, CAN},
volume = {10328 LNCS},
year = {2017}
}
@article{faucris.263692422,
abstract = {We study the complexity of computing the mixed-integer hull conv(P∩(^{Zn}×^{Rd})) of a polyhedron P. Given an inequality description, with one integer variable, the mixed-integer hull can have exponentially many vertices and facets in d. For n,d fixed, we give an algorithm to find the mixed-integer hull in polynomial time. Given a finite set V⊂Qn+^{d}, with n fixed, we compute a vertex description of the mixed-integer hull of conv(V) in polynomial time and give bounds on the number of vertices of the mixed-integer hull.},
author = {Hildebrand, Robert and Oertel, Timm and Weismantel, Robert},
doi = {10.1016/j.orl.2015.03.002},
faupublication = {no},
journal = {Operations Research Letters},
keywords = {Mixed-integer concave minimization; Mixed-integer hull; Polyhedron},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {279-282},
peerreviewed = {Yes},
title = {{Note} on the complexity of the mixed-integer hull of a polyhedron},
volume = {43},
year = {2015}
}
@article{faucris.263689155,
abstract = {We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the ℓ-norm of the vector. Our main results are new improved bounds on the minimal ℓ-norm of solutions to systems Ax= b, where A∈ Z^{m}^{×}^{n}, b∈ Z^{m} and x is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with ℓ-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over R, to other subdomains such as Z. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.},
author = {Aliev, Iskander and Averkov, Gennadiy and De Loera, Jesus A. and Oertel, Timm},
doi = {10.1007/s10107-021-01657-8},
faupublication = {no},
journal = {Mathematical Programming},
note = {CRIS-Team Scopus Importer:2021-09-09},
peerreviewed = {unknown},
title = {{Sparse} representation of vectors in lattices and semigroups},
year = {2021}
}
@inproceedings{faucris.263690153,
abstract = {We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equations, there exist LP feasible solutions with at most m many nonzero entries. We show that under relatively mild assumptions, integer programs in standard form have feasible solutions with O(m) many nonzero entries, on average. Our proof uses ideas from the theory of groups, lattices, and Ehrhart polynomials. From our main theorem we obtain the best known upper bounds on the integer Carathéodory number provided that the determinants in the data are small.},
author = {Oertel, Timm and Paat, Joseph and Weismantel, Robert},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
date = {2019-05-22/2019-05-24},
doi = {10.1007/978-3-030-17953-3{\_}26},
editor = {Andrea Lodi, Viswanath Nagarajan},
faupublication = {no},
isbn = {9783030179526},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {341-353},
peerreviewed = {unknown},
publisher = {Springer Verlag},
title = {{Sparsity} of {Integer} {Solutions} in the {Average} {Case}},
venue = {Ann Arbor, MI},
volume = {11480 LNCS},
year = {2019}
}
@article{faucris.263690410,
abstract = {The support of a vector is the number of nonzero components. We show that given anintegral m×n matrix A, the integer linear optimization problem maxfcT x: Ax = b; x = 0; x 2 Znghas an optimal solution whose support is bounded by 2m log(2pmkAk1), where kAk1 is the largestabsolute value of an entry of A. Compared to previous bounds, the one presented here is independentof the objective function. We furthermore provide a nearly matching asymptotic lower bound on thesupport of optimal solutions.},
author = {Aliev, I. and De Loera, J. A. and Eisenbrand, F. and Oertel, Timm and Weismantel, R.},
doi = {10.1137/17M1162792},
faupublication = {no},
journal = {SIAM Journal on Optimization},
keywords = {Integer linear programs; Sparse solutions; Support function},
note = {CRIS-Team Scopus Importer:2021-09-09},
pages = {2152-2157},
peerreviewed = {Yes},
title = {{The} support of integer optimal solutions},
volume = {28},
year = {2018}
}