Publications
of
Friedrich
Eisenbrand
Articles and
Bookchapters
- M Di Summa, F. Eisenbrand, Y. Faenza & C. Moldenhauer
On largest volume simplices and sub-determinants
ACM-SIAM Symposium on Discrete Algorithms (SODA 15)
to appear, 2015
- F. Eisenbrand &
Santosh Vempala
Geometric random edge
Manuscript, 2014
- F. Eisenbrand,
Dömötör Pálvölgyi & T. Rothvoß
Bin
packing via discrepancy of permutations
ACM Transactions on Algorithms 9(3): 24 (2013)
Invited to special issue of
ACM-SIAM Symposium on
Discrete Algorithms (SODA 11)
- Friedrich Eisenbrand, Nicolai
Hähnle,
Dömötör Pálvölgyi & Gennady
Shmonin,
Testing additive
integrality gaps.
Mathematical Programming, 141(1-2): 257-271, 2014 .
An extended abstract appeared in
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
(SODA10)
Austin, Texas, January 17-19, 2010.
-
F. Eisenbrand and N. Hähnle
Minimizing the number of lattice points in a translated polygon
Symposium of Discrete Algorithms (SODA 13), p. 1123-1130
-
N. Bonifas,
M. Di Summa,
F. Eisenbrand,
N. Hähnle,
M. Niemeier
On sub-determinants and the
diameter of polyhedra
Symposium of Computational Geometry (SoCG 12), p. 357-362
-
F. Eisenbrand and M. Niemeier
Coloring Fuzzy Circular
Interval Graphs
Eur. J. Comb. 33(5): 893-904 (2012)
- F. Eisenbrand, N. Kakimura, T. Rothvoss & L. Sanitá
Set covering with Ordered
Replacement: Additive and Multiplicative Gaps
Proceedings of the 15th Conference on Integer
Programming and Combinatorial Optimization (IPCO XV),
pp 170-187
New York, 2011
- F. Eisenbrand, Nicolai
Hähnle, Martin Niemeier
Covering
cubes and the closest vector problem
Proceedings of the 26th
Annual ACM Symposium on Computational Geometry 2011, pp 417-423
- Friedrich Eisenbrand, Nicolai
Hähnle, Alexander Razborov & Thomas
Rothvoß
Diameter
of
Polyhedra:
Limits
of
Abstraction
Mathematics of Operations Research
35(4): 786-794, 2010
This paper combines a result of the third author and an extended
abstract of the remaining authors that had appeared in
Proceedings of the 25th Annual ACM Symposium on Computational
Geometry (SoCG 2009)
Aarhus University, Denmark, June 8-10, 2009.
- F. Eisenbrand, F. Grandoni, T. Rothvoß, & G. Schäfer
Approximating
Connected Facility Location Problems via Random Facility Sampling and
Core Detouring.
Journal
of Computer and System Sciences (76):8, 709-726, 2010
An extended abstract appeared in
Proceedings of Nineteenth
annual
ACM-SIAM
symposium
on Discrete
algorithms (SODA 2008), pp 1174-1183.
- Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier,
Martin Skutella, José Verschae & Andreas Wiese
Scheduling periodic tasks in a hard real-time environment
Proceedings of the 37th International Colloquium on Automata,
Languages and Programming (ICALP 2010), pp. 299-311.
- Friedrich Eisenbrand, Karthikeyan Kesavan, Raju
Mattikalli,
Martin Niemeier, Arnold Nordsieck, Martin Skutella, Jose Verschae &
Andreas Wiese
Solving an Avionics Real-Time Scheduling Problem by Advanced
IP-Methods
Proceedings of the 18th Annual European
Symposium on Algorithms (ESA 2010), to appear.
- Friedrich Eisenbrand & Thomas
Rothvoß
EDF-schedulability
of
synchronous
periodic
task
systems is coNP-hard
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
(SODA10)
Austin, Texas, January 17-19, 2010.
- Friedrich Eisenbrand & T. Rothvoß
A PTAS for
Static Priority Real-Time Scheduling with Resource Augmentation
In procedings of the 35th International Colloquium on Automata,
Languages and Programming, (ICALP 08), pp 246-257.
- Friedrich Eisenbrand, Janos Pach, T. Rothvoß , &
Nir B. Sopher
Convexly
independent subsets of the Minkowski sum of planar point sets
Electronic Journal of Combinatorics, vol. 15.
- Friedrich Eisenbrand & T. Rothvoß
Static-priority
Real-time Scheduling: Response Time Computation is NP-hard
In procedings of the 29th IEEE Real-Time Systems Symposium (RTSS 08),
Barcelona, Nov. 30-3 Dec., 2008.
- Friedrich Eisenbrand, Fabrizio
Grandoni, Gianpaolo Oriolo & Martin
Skutella,
New Approaches for Virtual Private Network Design,
SIAM Journal on Computing 37(3):706-721, 2007.
An extended Abstract appeared as
New
Approaches
for
Virtual
Private
Network Design,
L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, M. Yung (Eds.):
Proceedings of the 32nd International Colloquium on Automata, Languages
and Programming (ICALP'05), Lecture Notes in Computer Science 3142,
Springer: Berlin, 2005, 1151-1162.
- Friedrich Eisenbrand, Andreas
Karrenbauer, Martin Skutella & Chihao
Xu,
Multiline
Addressing
by
Network
Flow,
in Yossi Azar & Thomas Erlebach (eds.): Proceedings of
the 14th Annual European Symposium on Algorithms (ESA'06), Lecture
Notes in Computer Science 4168, Springer: Berlin, 744--755, 2006.
- Friedrich Eisenbrand & Edda Happ,
Provisioning
a
virtual
private
network
under the presence of non-communicating groups,
T. Calamoneri, I. Finocchi, G. F. Italiano (Eds): Proceedings of the
6th Italian Conference on Algorithms and Complexity, CIAC 2006, Lecture
Notes in Computer Science 3998, Springer: Berlin, 2006, 105 - 114.
- F. Eisenbrand and S. Laue.
A
linear
algorithm
for
integer
programming in the plane.
Mathematical Programming, 102(2):249-259, 2005. (Slides)
An extended abstract appeared as:
A faster algorithm for two variable integer programming.
In 14th Annual International Symposium on Algorithms and Computation
(ISAAC 03), LNCS. Springer, 2003.
- Bernd Becker, Markus Behle,
Friedrich
Eisenbrand
&
Ralf Wimmer,
BDDs
in
a
Branch
and
Cut Framework,
Sotiris E. Nikoletseas (eds.):Proceedings of the 4th
International Workshop on Efficient and Experimental Algorithms (WEA 05),
Lecture
Notes
in
Computer
Science 3503, Springer: Berlin, 2005, 452-463
.
- Friedrich Eisenbrand, Stefan Funke,
Andreas
Karrenbauer, Elmar Schömer & Joachim Reichel
Packing
a
trunk
-
now
even with a twist,
L. Kobbelt, V. Shapiro (Eds.): Proceedings of the Ninth
ACM Symposium on Solid and Physical Modeling (SPM 2005), 197-206
- F. Eisenbrand, S. Funke, A. Karrenbauer and D. Matjevic.
Energy-aware
stage
illumination.
J. S. B. Mitchell, G. Rote (Eds.): Proceedings of the 21st ACM
Symposium on Computational Geometry (SoCG 05), Pisa, Italy, 2005,
336-345.
- F. Eisenbrand and F. Grandoni.
An
improved
approximation
algorithm
for
virtual private network design.
in Proceedings of Sixteenth annual ACM-SIAM symposium on Discrete
algorithms (SODA 05), 928-932.
- F. Eisenbrand.
Fast
integer
programming
in
fixed
dimension.
In G. Di Battista and U. Zwick, editors, In Proceedings of the 11th
Annual European Symposium on Algorithms (ESA 03), volume 2832 of
LNCS, pages 196-207. Springer, 2003. (Slides)
- E. Althaus, F. Eisenbrand, S. Funke,
and K.
Mehlhorn.
Point
containment
in
the
integer
hull of a polyhedron.
In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete
algorithms (SODA 04), 2004.
- F. Eisenbrand and A. S. Schulz.
Bounds
on
the
Chvátal
rank
of polytopes in the 0/1 cube.
Combinatorica, 23(2):245-261, 2003.
An extended abstract appeared as:
Bounds on the Chvátal rank of polytopes in the 0/1 cube.
In G. Cornuéjols, R. E. Burkard, and G. J. Woeginger, editors, Integer
Programming and Combinatorial Optimization (IPCO 99), pages 137-150.
Springer, LNCS 1610, 1999.
- Friedrich Eisenbrand & Fabrizio Grandoni,
On the complexity of fixed parameter clique and dominating set,
Theoretical Computer Science, 326(1-3): 57-67, 2004.
- F. Eisenbrand, S. Funke, N. Garg,
and
J.
Könemann.
A combinatorial algorithm for computing a maximum independent set in a
t-perfect graph.
In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete
algorithms (SODA 03), pages 517-522. Society for Industrial and Applied
Mathematics, 2003.
- P. Ventura and F. Eisenbrand.
A compact linear program for testing optimality of perfect matchings.
Operations Research Letters, 31(6):429-434, 2003.
- F. Eisenbrand and F. Grandoni.
Detecting directed 4-cycles still faster.
Information Processing Letters, 87(1):13-15, 2003.
- F. Eisenbrand, G. Rinaldi, and P. Ventura.
Primal
separation
for
0/1
polytopes.
Mathematical Programming, 95(3):475-491, 2003.
An extended abstract appeared as:
0/1 optimization and 0/1 primal separation are equivalent.
In Proceedings of the thirteenth annual ACM-SIAM symposium on discrete
algorithms (SODA 02), pages 920-926, 2002.
- A.
Bockmayr and F. Eisenbrand.
Cutting planes and the elementary closure in fixed dimension.
Mathematics of Operations Research, 26(2):304-312, 2001.
- F. Eisenbrand.
Short
vectors
of
planar
lattices
via continued fractions.
Information Processing Letters, 79(3):121-126, 2001.
- F. Eisenbrand and G. Rote.
Fast
reduction
of
ternary
quadratic
forms.
In J. Silverman, editor, Cryptography and Lattices Conference, CALC
2001, volume 2146 of LNCS, pages 32-44. Springer, 2001.
- F. Eisenbrand and G. Rote.
Fast
2-variable
integer
programming.
In K. Aardal and B. Gerards, editors, Integer Programming and
Combinatorial Optimization (IPCO 2001), volume 2081 of LNCS, pages
78-89. Springer, 2001.
- A.
Bockmayr and F. Eisenbrand.
Combining logic and optimization in cutting plane theory.
In H. Kirchner and C. Ringeissen, editors, Frontiers of Combining
Systems, FroCoS 2000, LNAI 1794, pages 1-17. Springer, 2000.
invited paper.
- F. Eisenbrand.
On
the
membership
problem
for
the elementary closure of a polyhedron.
Combinatorica, 19(2):297-300, 1999.
- A.
Bockmayr, F. Eisenbrand, M. E. Hartmann, and A. S. Schulz.
On the Chvátal rank of polytopes in the 0/1 cube.
Discrete Applied Mathematics, 98:21-27, 1999.
- J. Buchmann and F. Eisenbrand.
On factor refinement in number fields.
Mathematics of Computation, 68(225):345-350, 1999.
Theses