5 papers
Polynomial Matrices in Integer Programming With Restricted Subdeterminants
Marcel Celaya, Stefan Kuhlmann, Robert Weismantel
We introduce a framework for tackling questions in discrete optimization associated with parametric constraint matrices. More precisely, the constraint matrices have entries that a…
Alternating Linear Minimization: Revisiting von Neumann's alternating projections
Gábor Braun, Sebastian Pokutta, Robert Weismantel
In 1933 von Neumann proved a beautiful result that one can approximate a point in the intersection of two convex sets by alternating projections, i.e., successively projecting on o…
A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
Stefan Kuhlmann, Robert Weismantel
One important question in the theory of lattices is to detect a shortest vector: given a norm and a lattice, what is the smallest norm attained by a non-zero vector contained in th…
Sparse Approximation in Lattices and Semigroups
Stefan Kuhlmann, Timm Oertel, Robert Weismantel
This paper deals with the following question: Suppose that there exist an integer or a non-negative integer solution to a system , where the number of non-zero componen…
Forall-exist statements in pseudopolynomial time
Eleonore Bach, Friedrich Eisenbrand, Thomas Rothvoss +1
Given a convex set and an integer matrix , we consider statements of the form s.t. $Wx \leq…