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.


These authors try to minimize the number k of permutation matrices that are needed to decompose a specific DS matrix and show that this problem is NP-hard: https://hal.inria.fr/hal-01270331v2/document


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.