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…