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

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

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

Coloring fuzzy circular interval graphs

Friedrich Eisenbrand, Martin Niemeier

Given a graph G with nonnegative node labels w, a multiset of stable sets S_1,...,S_k\subseteq V(G) such that each vertex v \in V(G) is contained in w(v) many of these stable sets is called a weighted coloring. The weighted coloring number \chi_w(G) is the ...

Elsevier2012

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

Siam, 3600 Univ City Science Center, Philadelphia, Pa 19104-2688 Usa2011

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

Testing additive integrality gaps

Friedrich Eisenbrand, Nicolai Hähnle, Gennady Shmonin

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

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods

Friedrich Eisenbrand, Martin Niemeier

We report on the solution of a real-time scheduling problem that arises in the design of software-based operation control of aircraft. A set of tasks has to be distributed on a minimum number of machines and offsets of the tasks have to be computed. The ta ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

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. Even if this abstraction is more general than other abstractions previously studied in the literature, known upper bounds on the diameter of polyhedra continue to hold her ...

2010

EDF-schedulability of synchronous periodic task systems is coNP-hard

Friedrich Eisenbrand, Thomas Rothvoss

In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) i ...

2010

Friedrich Eisenbrand

Graph Chatbot

Chat with Graph Search

Bin Packing via Discrepancy of Permutations

Testing additive integrality gaps

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

Coloring fuzzy circular interval graphs

Bin Packing via Discrepancy of Permutations

Covering Cubes and the Closest Vector Problem

Testing additive integrality gaps

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods

Diameter of Polyhedra: Limits of Abstraction

EDF-schedulability of synchronous periodic task systems is coNP-hard

Bin Packing via Discrepancy of Permutations

Testing additive integrality gaps

EDF-schedulability of synchronous periodic task systems is coNP-hard

Coloring fuzzy circular interval graphs

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

Bin Packing via Discrepancy of Permutations

Covering Cubes and the Closest Vector Problem

Testing additive integrality gaps

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods

Diameter of Polyhedra: Limits of Abstraction