Recherche

Afficher tous les résultats pour

Accueil

Personne

Friedrich Eisenbrand

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (36)

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

On sub-determinants and the diameter of polyhedra

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

2012

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

Real-time Avionics OptimizationMathematische Optimierung von Echtzeitsystemen im Flugzeugdesign

Friedrich Eisenbrand, Martin Niemeier

De Gruyter, Oldenbourg Wissenschaftsverlag GmbH2011

Covering Cubes and the Closest Vector Problem

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier

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

Scheduling periodic tasks in a hard real-time environment

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier

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

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin, 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

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

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

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

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

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

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

Convexly independent subsets of the Minkowski sum of planar point sets

János Pach, Friedrich Eisenbrand, Thomas Rothvoss

Let P and Q be finite sets of points in the plane. In this note we consider the largest cardinality of a subset of the Minkowski sum S ⊆ P⊕Q which consist of convex independent points. We show that, if P and Q contain at most n points, then |S| = O(n^(4/3) ...

American Mathematical Society2008

Parametric integer programming in fixed dimension

Friedrich Eisenbrand, Gennady Shmonin

We consider the following problem: Given a rational matrix

A \in \mathbb{Q}^{m \times n}

and a rational polyhedron

Q \subseteq \mathbb{R}^{m+p}

, decide if for all vectors

b \in \mathbb{R}^m

, for which there exists an integral

z \in \mathbb{Z}^p

suc ...

2008

Static-priority Real-time Scheduling: Response Time Computation is NP-hard

Friedrich Eisenbrand, Thomas Rothvoss

IEEE Computer Society2008

Page 2 sur 2