Robert Weismantel

SODA Conference 2025 Conference Paper

Forall-exist statements in pseudopolynomial time

• Eleonore Bach
• Friedrich Eisenbrand
• Thomas Rothvoss
• Robert Weismantel

SODA Conference 2021 Conference Paper

Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

• Jana Cslovjecsek
• Friedrich Eisenbrand
• Christoph Hunkenschröder
• Lars Rohwedder
• Robert Weismantel

We consider integer and linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent and efficiently solvable sub-problems if a small number of constraints is deleted. A prominent example are n-fold integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within ℓ 1 -distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with n -fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.

SODA Conference 2018 Conference Paper

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

• Friedrich Eisenbrand
• Robert Weismantel

We consider integer programming problems in standard form max{ c T x: Ax = b, x ≥ 0, x ∊ ℤ n } where A ∊ ℤ m×n, b ∊ ℤ m and c ∊ ℤ n. We show that such an integer program can be solved in time ( m ·Δ) O ( m ) · || b || ∞ 2, where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou (1981) of ( m · Δ) O ( m 2), where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in ℝ m that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by m. We also use the Steinitz lemma to show that the ℓ 1 -distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by m · (2 m · Δ + 1) m. Here Δ is again an upper bound on the absolute values of the entries of A. The novel strength of our bound is that it is independent of n. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.

STOC Conference 2017 Conference Paper

A strongly polynomial algorithm for bimodular integer linear programming

• Stephan Artmann
• Robert Weismantel
• Rico Zenklusen

We present a strongly polynomial algorithm to solve integer programs of the form max{ c T x : Ax ≤ b , x εℤ n }, for A εℤ m X n with rank ( A )= n , b ε≤ m , c ε≤ n , and where all determinants of ( n X n )-sub-matrices of A are bounded by 2 in absolute value. In particular, this implies that integer programs max{ c T x : Q x ≤ b , x εℤ ≥0 n }, where Q ε ℤ m X n has the property that all subdeterminants are bounded by 2 in absolute value, can be solved in strongly polynomial time. We thus obtain an extension of the well-known result that integer programs with constraint matrices that are totally unimodular are solvable in strongly polynomial time.

SODA Conference 2017 Conference Paper

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

• Robert Hildebrand
• Robert Weismantel
• Rico Zenklusen

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on n vertices, with a polynomial number of constraints, requires many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first nontrivial lower bound on the number of integer variables needed in such settings.

SODA Conference 2016 Conference Paper

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

• Robert Hildebrand
• Robert Weismantel
• Kevin Zemmer

We present a generic approach that allows us to develop a fully polynomial-time approximation scheme (FTPAS) for minimizing nonlinear functions over the integer points in a rational polyhedron in fixed dimension. The approach combines the subdivision strategy of Papadimitriou and Yannakakis [22] with ideas similar to those commonly used to derive real algebraic certificates of positivity for polynomials. Our general approach is widely applicable. We apply it, for instance, to the Motzkin polynomial and to indefinite quadratic forms x T Q x in a fixed number of variables, where Q has at most one positive, or at most one negative eigenvalue. In dimension three, this leads to an FPTAS for general Q.

SODA Conference 2014 Conference Paper

Integer quadratic programming in the plane

• Alberto Del Pia
• Robert Weismantel

We show that the problem of minimizing a quadratic polynomial with integer coefficients over the integer points in a general two-dimensional rational polyhedron is solvable in time bounded by a polynomial in the input size.

TCS Journal 2011 Journal Article

An algorithmic framework for network reconstruction

• Markus Durzinsky
• Annegret Wagler
• Robert Weismantel

Models of biological systems and phenomena are of high scientific interest and practical relevance, but not always easy to obtain due to their inherent complexity. To gain the required insight, experimental data are provided and need to be interpreted in terms of models that explain the observed phenomena. In systems biology the framework of Petri nets is often used to describe models for the regulatory mechanisms of biological systems. The aim of this paper is to provide, based on results in Marwan et al. (2008) [1] and Durzinsky et al. (2008) [2], an algorithmic framework for the challenging task of generating all possible Petri nets fitting the given experimental data.

SODA Conference 2006 Conference Paper

FPTAS for mixed-integer polynomial optimization with a fixed number of variables

• Jesús A. De Loera
• Raymond Hemmecke
• Matthias Köppe
• Robert Weismantel

SODA Conference 1999 Conference Paper

An Oracle-Polynomial Time Augmentation Algorithm for Integer Programming

• Andreas S. Schulz
• Robert Weismantel