Showing cs.DSShow all
3 papers · 1 filter
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.DS2024
Lift-and-Project Integrality Gaps for Santa Claus
Etienne Bamas
This paper is devoted to the study of the MaxMinDegree Arborescence (MMDA) problem in layered directed graphs of depth , which is an important specia…
cs.DS2024
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…