4 citations · 11 across the 8 of their papers we have counts for
14 papers
Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes
Max Hahn-Klimroth, Dominik Kaaser, Malin Rau
In the pooled data problem we are given agents with hidden state bits, either or . The hidden states are unknown and can be seen as the underlying ground truth . To u…
Dynamic Averaging Load Balancing on Arbitrary Graphs
Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour +2
In this paper we study dynamic averaging load balancing on general graphs. We consider infinite time and dynamic processes, where in every step new load items are assigned to rando…
Scheduling with Many Shared Resources
Max A. Deppert, Klaus Jansen, Marten Maack +2
Consider the many shared resource scheduling problem where jobs have to be scheduled on identical parallel machines with the goal of minimizing the makespan. However, each job need…
Inference of a Rumor's Source in the Independent Cascade Model
Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser +2
We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al.\ [2003]. In this model, a small subset of nodes from a net…
On the Hierarchy of Distributed Majority Protocols
Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard +3
We study the Consensus problem among agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in whi…
Asynchronous Opinion Dynamics in Social Networks
Petra Berenbrink, Martin Hoefer, Dominik Kaaser +3
Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well…
Closing the gap for single resource constraint scheduling
Klaus Jansen, Malin Rau
In the problem called single resource constraint scheduling, we are given identical machines and a set of jobs, each needing one machine to be processed as well as a share of a…
Peak Demand Minimization via Sliced Strip Packing
Max A. Deppert, Klaus Jansen, Arindam Khan +2
We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedu…
Solving Packing Problems with Few Small Items Using Rainbow Matchings
Max Bannach, Sebastian Berndt, Marten Maack +4
An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been st…
Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing
Klaus Jansen, Malin Rau
We study the Multiple Cluster Scheduling problem and the Multiple Strip Packing problem. For both problems, there is no algorithm with approximation ratio better than unless $P…
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…
Closing the gap for pseudo-polynomial strip packing
Klaus Jansen, Malin Rau
The set of 2-dimensional packing problems builds an important class of optimization problems and Strip Packing together with 2-dimensional Bin Packing and 2-dimensional Knapsack is…
Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
Sören Henning, Klaus Jansen, Malin Rau +1
We study the Parallel Task Scheduling problem with a constant number of machines. This problem is known to be strongly NP-complete for each , while i…
Improved approximation for two dimensional strip packing with polynomial bounded width
Klaus Jansen, Malin Rau
We study the well-known two-dimensional strip packing problem. Given is a set of rectangular axis-parallel items and a strip of width with infinite height. The objective is to…