Friedrich Eisenbrand

activity

20232026

collaborators

5 papers

math.OC2026

Polyhedral extended formulations that approximate the Gomory closure for packing problems

Friedrich Eisenbrand, Samuel Fiorini, Lars Rohwedder +1

We consider $0/1$ packing problems $max {c^{T} x : A x \leq 1, x \in {0, 1}^{n}}$ , with $A \in R_{\geq 0}^{m \times n}$ . A way to solve such problems is via tighteni…

cs.DM2025

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi +2

For a real matrix $A \in R^{d \times n}$ with non-collinear columns, we show that $n \leq O (d^{4} κ_{A})$ where $κ_{A}$ is the \emph{circuit imbalance measure} of $A$ . The circu…

physics.chem-ph2024

Integer linear programming for unsupervised training set selection in molecular machine learning

Matthieu Haeberle, Puck van Gerwen, Ruben Laplaza +4

Integer linear programming (ILP) is an elegant approach to solve linear optimization problems, naturally described using integer decision variables. Within the context of physics-i…

cs.DS2024

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems

Friedrich Eisenbrand, Lars Rohwedder, Karol Węgrzycki

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 ${- Δ, \dots, Δ}$ or more generally $m…

cs.CG2023

An improved bound on sums of square roots via the subspace theorem

Friedrich Eisenbrand, Matthieu Haeberle, Neta Singer

The sum of square roots is as follows: Given $x_{1}, \dots, x_{n} \in Z$ and $a_{1}, \dots, a_{n} \in N$ decide whether $E = \sum_{i = 1}^{n} x_{i} a_{i} \geq 0$ . It is a promi…