Personne
Klaus Jansen
Cette personne n’est plus à l’EPFL
Publications associées (4)
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 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 HEIDELBERG2020A note on the integrality gap of the configuration LP for restricted Santa Claus
In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...
ELSEVIER2020Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability
Ola Nils Anders Svensson, Klaus Jansen
We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...
Assoc Computing Machinery2012