Publications de Kim-Manuel Klein

Reducibility bounds of objective functions over the integers

We study the settings where we are given a separable objective function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a new function with a much smaller domain. Our results appl ...

Elsevier2023

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Fully dynamic bin packing revisited

Kim-Manuel Klein, Klaus Jansen

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. ...

SPRINGER HEIDELBERG2020

FCC Physics Opportunities: Future Circular Collider Conceptual Design Report Volume 1

Pierluigi Bruzzone, Jan Steggemann, Elena Graverini, Jean-Michel Sallese, Thomas Rizzo, Luca Rossi, Rui Ning Wang, Fabio Avino, Xavier Buffat, Tatiana Pieloni

We review the physics opportunities of the Future Circular Collider, covering its e(+)e(-), pp, ep and heavy ion programmes. We describe the measurement capabilities of each FCC component, addressing the study of electroweak, Higgs and strong interactions, ...

2019

Faster Algorithms for Integer Programs with Block Structure

Friedrich Eisenbrand, Kim-Manuel Klein, Christoph Hunkenschröder

We consider integer programming problems max {c^Tx : A x = b, l

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2018

Using Structural Properties for Integer Programs

Kim-Manuel Klein

Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, ...

SPRINGER INTERNATIONAL PUBLISHING AG2018