3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
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…