5 papers
Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
Tatiana Rocha Avila, Lars Rohwedder, Leo Wennmann
Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong [ITCS'26] introduced a generalization of classical discrepancy theory to non-a…
Graph Scheduling with Group Completion Times
Lars Rohwedder, Leander Schnaars
In the Graph Scheduling problem we schedule a given multiset of edges on discrete time steps, such that at each step the set of edges forms a matching. The goal is to minimize the…
Randomized Rounding over Dynamic Programs
Etienne Bamas, Shi Li, Lars Rohwedder
We show that under mild assumptions for a problem whose solutions admit a dynamic programming-like recurrence relation, we can still find a solution under additional packing constr…
Cost Preserving Dependent Rounding for Allocation Problems
Lars Rohwedder, Arman Rouhani, Leo Wennmann
We present a dependent randomized rounding scheme, which rounds fractional solutions to integral solutions satisfying certain hard constraints on the output while preserving Cherno…
3.415-Approximation for Coflow Scheduling via Iterated Rounding
Lars Rohwedder, Leander Schnaars
We provide an algorithm giving a ()-approximation for Coflow Scheduling and a -approximation for Coflow Scheduling with release dates. This improves u…