8 papers · 1 filter
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…
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-…
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…