Revisiting the Marginal Distribution Model: Extensions and Generalizations


Building on previous work which incorporated the Marginal Distribution Model to examine the persistency problem for discrete optimization, we provide extensions in two ways. Firstly, we extend the distributionally robust problem to now incorporate completely arbitrary marginal distributions, and we find a dual optimization problem that not only points the way to tractable cases but also presents a basic multi-marginal transport problem with a story not unlike that found in the assignment game from mathematical economics. Secondly, we investigate the role of the discrete constraint set’s structure in tractability. As well, we consider how the results generalize/unify some other works.