Publications de Friedrich Eisenbrand

Integer Linear Programming for Unsupervised Training Set Selection in Molecular Machine Learning

Anne-Clémence Corminboeuf, Friedrich Eisenbrand, Puck Elisabeth van Gerwen, Ksenia Briling, Rubén Laplaza Solanas, Jan Weinreich

Integer linear programming (ILP) is an elegant approach to solve linear optimization problems, naturally described using integer decision variables. Within the context of physics-inspired machine learning (ML) applied to chemistry, we demonstrate the relev ...

IOP Publishing Ltd2025

Integer points in the degree-sequence polytope

Friedrich Eisenbrand, Rom Pinchasi

An integer vector 𝑏 ∈ Z𝑑 is a degree sequence if there exists a hypergraph with vertices {1, … , 𝑑} such that each 𝑏𝑖 is the number of hyperedges containing 𝑖. The degree-sequence polytope 𝒵 𝑑 is the convex hull of all degree sequences. We show that all bu ...

ELSEVIER2025

Forall-exist statements in pseudopolynomial time

Friedrich Eisenbrand

Given a convex set Q ⊆ R m and an integer matrix W ∈ Z m×n , we consider statements of the form ∀b ∈ Q ∩ Z m ∃x ∈ Z n s.t. W x ≤ b. Such statements can be verified in polynomial time with the algorithm of Kannan and its improvements if n is fixed and Q is ...

Society for Industrial and Applied Mathematics2025

From approximate to exact integer programming

Friedrich Eisenbrand

Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c)+ c which is K, scaled by 2 from its center of ...

Springer Heidelberg2024

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems

Friedrich Eisenbrand, Lars Rohwedder

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from

\{-\Delta,\ldots,\Delta\}

or more generally

m

-dimensional vectors of such discrete values. We resolve the para ...

IEEE2024

An Improved Bound on Sums of Square Roots via the Subspace Theorem

Friedrich Eisenbrand

The sum of square roots is as follows: Given x1, . . ., xn ∈ Z and a1, . . ., an ∈ N decide whether E = Pni=1 xi √ai ≥ 0. It is a prominent open problem (Problem 33 of the Open Problems Project), whether this can be decided in polynomial time. The state-of ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Reducibility bounds of objective functions over the integers

Friedrich Eisenbrand, Kim-Manuel Klein

We study the settings where we are given a separable objective function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a new function with a much smaller domain. Our results appl ...

Elsevier2023

Metric learning for kernel ridge regression: assessment of molecular similarity

Anne-Clémence Corminboeuf, Friedrich Eisenbrand, Puck Elisabeth van Gerwen, Raimon Fabregat I De Aguilar-Amat

Supervised and unsupervised kernel-based algorithms widely used in the physical sciences depend upon the notion of similarity. Their reliance on pre-defined distance metrics-e.g. the Euclidean or Manhattan distance-are problematic especially when used in c ...

IOP Publishing Ltd2022

Approximate CVPp in time 2(0.802n)

Friedrich Eisenbrand, Moritz Andreas Venzin

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

An Improved Analysis of Local Search for Max-Sum Diversification

Rico Zenklusen, Friedrich Eisenbrand, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

Faster Algorithms for Integer Programs with Block Structure

Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein

We consider integer programming problems max {c^Tx : A x = b, l

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2018

The Support Of Integer Optimal Solutions

Friedrich Eisenbrand

The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m ...

SIAM PUBLICATIONS2018

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

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2018

On largest volume simplices and sub-determinants

Friedrich Eisenbrand, Marco Di Summa, Carsten Moldenhauer, Yuri Faenza

2015

On Sub-determinants and the Diameter of Polyhedra

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Nicolas Bonifas, Marco Di Summa

We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show ...

Springer2014

Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Friedrich Eisenbrand

This paper features two main contributions. On the one hand, it gives an impressive survey on the progress on the diameter problem, including the breakthrough of the author with his disproof of the Hirsch conjecture among many other recent results. On the ...

Springer2013

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Association for Computing Machinery2013

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin, Nicolai Hähnle

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in ...

Springer Berlin Heidelberg2013