Randomized Rounding over Dynamic Programs

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 constraints, which need to be satisfied approximately. The number of additional constraints can be very large, e.g., polynomial in the problem size. Technically, we reinterpret the dynamic programming subproblems and their solutions as a network design problem. Inspired by techniques from, e.g., the Directed Steiner Tree problem, we construct a strong LP relaxation, on which we then apply randomized rounding. Our approximation guarantees on the packing constraints have roughly the form of a (nє polylog n)-approximation in time nO(1/є), for any є > 0. By setting є=loglogn/logn, we obtain a polylogarithmic approximation in quasi-polynomial time, or by setting є as a constant, an nє-approximation in polynomial time.