Given a doubly-stochastic matrix $\pi$, Birkhoff-von Neumann theorem states that $\pi$ can be written as a convex combination of permutation matrices:
$$\pi=\sum_{i\leq k} \alpha_i B_i$$
where $\sum_{i \leq k} \alpha_i$ = 1 and $B_i$ are the permutation matrices. Such decomposition is generally not unique. I am looking for an algorithm that finds a particular decomposition that maximizes some objective. For example, suppose that for each $i$ there is a scalar $r_i$. I wish to find a decomposition s.t. $\sum_{i\leq k} \alpha_i r_i$ is maximized.
I would also be interested in an approximation algorithm or a heuristic.
