Optimization over Young Diagrams

Abstract

We consider the problem of finding a Young diagram minimizing the sum of evaluations of a given pair of functions on the parts of the associated pair of conjugate partitions. While there are exponentially many diagrams, we show it is polynomial time solvable.