11 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…