34 citations · 35 across the 7 of their papers we have counts for
16 papers
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
Kim-Manuel Klein, Adam Polak, Lars Rohwedder
The starting point of this paper is the problem of scheduling jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy…
Collapsing the Tower -- On the Complexity of Multistage Stochastic IPs
Kim-Manuel Klein, Janina Reuter
In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) - so called multistage stochastic IPs. A multistage stochastic IP…
On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem
Kim-Manuel Klein
Consider positive integral solutions to the equation . In the so called unbounded subset sum problem, the objective is to d…
The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs
Klaus Jansen, Kim-Manuel Klein, Alexandra Lassota
We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called -stage stochastic. A -st…
New Bounds for the Vertices of the Integer Hull
Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein
The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-…
Fuzzy Simultaneous Congruences
Max A. Deppert, Klaus Jansen, Kim-Manuel Klein
We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer that is specified by fixed rem…
An Algorithmic Theory of Integer Programming
Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein +3
We study the general integer programming problem where the number of variables is a variable part of the input. We consider two natural parameters of the constraint matrix :…
About the Complexity of Two-Stage Stochastic IPs
Kim-Manuel Klein
We consider so called -stage stochastic integer programs (IPs) and their generalized form of multi-stage stochastic IPs. A -stage stochastic IP is an integer program of the f…
An EPTAS for machine scheduling with bag-constraints
Kilian Grage, Klaus Jansen, Kim Manuel Klein
Machine scheduling is a fundamental optimization problem in computer science. The task of scheduling a set of jobs on a given number of machines and minimizing the makespan is well…
Faster Algorithms for Integer Programs with Block Structure
Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein
We consider integer programming problems where has a (recursive) block-structure general…
Empowering the Configuration-IP New PTAS Results for Scheduling with Setups Times
Klaus Jansen, Kim-Manuel Klein, Marten Maack +1
Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to b…
Online Strip Packing with Polynomial Migration
Klaus Jansen, Kim-Manuel Klein, Maria Kosche +1
We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing heig…
Closing the Gap for Makespan Scheduling via Sparsification Techniques
Klaus Jansen, Kim-Manuel Klein, José Verschae
Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of $n…
About the Structure of the Integer Cone and its Application to Bin Packing
Klaus Jansen, Kim-Manuel Klein
We consider the bin packing problem with different item sizes and revisit the structure theorem given by Goemans and Rothvoß[6] about solutions of the integer cone. We present…
Fully Dynamic Bin Packing Revisited
Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein
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, t…
A Robust AFPTAS for Online Bin Packing with Polynomial Migration
Klaus Jansen, Kim-Manuel Klein
In this paper we develop general LP and ILP techniques to find an approximate solution with improved objective value close to an existing solution. The task of improving an approxi…