Person
Kim-Manuel Klein
This person is no longer with EPFL
Related publications (5)
Reducibility bounds of objective functions over the integers
Friedrich Eisenbrand, Kim-Manuel Klein
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 ...
Amsterdam2023The 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 HEIDELBERG2022Fully 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 HEIDELBERG2020Faster 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 Informatik2018Using Structural Properties for Integer Programs
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