14 citations · 21 across the 20 of their papers we have counts for
32 papers
Polyhedral extended formulations that approximate the Gomory closure for packing problems
Friedrich Eisenbrand, Samuel Fiorini, Lars Rohwedder +1
We consider packing problems , with . A way to solve such problems is via tighteni…
ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
Lars Rohwedder
Given jobs with processing times and machines with speeds our goal is to allocate the jobs to machines minimi…
Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
Lars Rohwedder, Ashkan Safari, Tjark Vredeveld
Local search is a widely used technique for tackling challenging optimization problems, offering simplicity and strong empirical performance across various problem domains. In this…
Space-Efficient Algorithm for Integer Programming with Few Constraints
Lars Rohwedder, Karol Węgrzycki
Integer linear programs , where , , and , can be solved…
Fine-Grained Equivalence for Problems Related to Integer Linear Programming
Lars Rohwedder, Karol Węgrzycki
Integer Linear Programming with binary variables and many -constraints can be solved in time and it is open whether the dependence o…
The Submodular Santa Claus Problem
Etienne Bamas, Sarah Morell, Lars Rohwedder
We consider the problem of allocating indivisible resources to players so as to maximize the minimum total value any player receives. This problem is sometimes dubbed the Santa Cla…
A k-swap Local Search for Makespan Scheduling
Lars Rohwedder, Ashkan Safari, Tjark Vredeveld
Local search is a widely used technique for tackling challenging optimization problems, offering significant advantages in terms of computational efficiency and exhibiting strong e…
Simpler constant factor approximation algorithms for weighted flow time -- now for any -norm
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time…
Santa Claus meets Makespan and Matroids: Algorithms and Reductions
Étienne Bamas, Alexander Lindermayr, Nicole Megow +2
In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation,…
Optimizing Low Dimensional Functions over the Integers
Daniel Dadush, Arthur Léonard, Lars Rohwedder +1
We consider box-constrained integer programs with objective , where is a "complicated" function with an dimensional domain. Here we assume we have …
Better Trees for Santa Claus
Étienne Bamas, Lars Rohwedder
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes…
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…
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
An important objective in scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs where each job is characterized by a release time, a proce…
Flow Time Scheduling and Prefix Beck-Fiala
Nikhil Bansal, Lars Rohwedder, Ola Svensson
We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction t…
Cardinality Constrained Scheduling in Online Models
Leah Epstein, Alexandra Lassota, Asaf Levin +2
Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham's…
Towards Non-Uniform k-Center with Constant Types of Radii
Xinrui Jia, Lars Rohwedder, Kshiteej Sheth +1
In the Non-Uniform k-Center problem we need to cover a finite metric space using k balls of different radii that can be scaled uniformly. The goal is to minimize the scaling factor…
Load Balancing: The Long Road from Theory to Practice
Sebastian Berndt, Max A. Deppert, Klaus Jansen +1
There is a long history of approximation schemes for the problem of scheduling jobs on identical machines to minimize the makespan. Such a scheme grants a -approximation sol…
Knapsack and Subset Sum with Small Items
Adam Polak, Lars Rohwedder, Karol Węgrzycki
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomi…
The Submodular Santa Claus Problem in the Restricted Assignment Case
Etienne Bamas, Paritosh Garg, Lars Rohwedder
The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned…
A -approximation algorithm for preemptive weighted flow time on a single machine
Lars Rohwedder, Andreas Wiese
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input cons…
Learning Augmented Energy Minimization via Speed Scaling
Étienne Bamas, Andreas Maggiori, Lars Rohwedder +1
As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a…
Additive Approximation Schemes for Load Balancing Problems
Moritz Buchem, Lars Rohwedder, Tjark Vredeveld +1
In this paper we introduce the concept of additive approximation schemes and apply it to load balancing problems. Additive approximation schemes aim to find a solution with an abso…
The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
Etienne Bamas, Paritosh Garg, Lars Rohwedder
We consider hypergraphs on vertices where each hyperedge contains exactly one vertex in . Our goal is to select a matching that covers all of , but we allow each se…
Robust Algorithms under Adversarial Injections
Paritosh Garg, Sagar Kale, Lars Rohwedder +1
In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the wo…