Friedrich Eisenbrand

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

Friedrich Eisenbrand

Chat with Graph Search

Covering Cubes and the Closest Vector Problem

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

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

An Improved Analysis of Local Search for Max-Sum Diversification

Testing additive integrality gaps

Integer points in the degree-sequence polytope

New Hardness Results for Diophantine Approximation

From approximate to exact integer programming

Forall-exist statements in pseudopolynomial time

Metric learning for kernel ridge regression: assessment of molecular similarity

On Sub-determinants and the Diameter of Polyhedra

Bin Packing via Discrepancy of Permutations

Diameter of Polyhedra: Limits of Abstraction

Coloring Fuzzy Circular Interval Graphs

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

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

Scheduling periodic tasks in a hard real-time environment

Connected facility location via random facility sampling and core detouring

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

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems