Publications by Friedrich Eisenbrand

Related publications (36)

Covering Cubes and the Closest Vector Problem

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n))(log(1/epsilon ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

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

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

An Improved Analysis of Local Search for Max-Sum Diversification

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

Testing additive integrality gaps

Friedrich Eisenbrand, Doemoetoer Palvoelgyi, Nicolai Hähnle

We consider the problem of testing whether the maximum 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 polynomi ...

2010

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

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

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 Heidelberg2025

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

Metric learning for kernel ridge regression: assessment of molecular similarity

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

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

On Sub-determinants and the Diameter of Polyhedra

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

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

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

Diameter of Polyhedra: Limits of Abstraction

Friedrich Eisenbrand, Thomas Rothvoss, Nicolai Hähnle

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best upper bounds on the diameter of polyhedra continue to ...

2009

Coloring Fuzzy Circular Interval Graphs

Friedrich Eisenbrand, Martin Niemeier

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...

Elsevier2009

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

Friedrich Eisenbrand, Matthieu Nicolas Haeberle, Neta Singer

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

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

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

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

Scheduling periodic tasks in a hard real-time environment

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks

\tau_i=(c_i,p_i)

on a minimum number of identical machines a ...

Springer-Verlag2010

Connected facility location via random facility sampling and core detouring

Friedrich Eisenbrand, Thomas Rothvoss

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...

2010

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