Before revision:  or (ii) low-rank interactions and sparse interactions. We also provide strong evidence that (iii)repulsive costs make MOT intractable by showing that several such problemsof interest are NP-hard to solve--even approximately. These three structures are quite general, and collectively they encompass many (if not most) current MOT applications.
After revision:  or (ii) low-rank and sparse components. These two structures encompass many--if not most--current applications of MOT. In addition to providing the first poly(n,k)-time algorithms for a wide range of MOT problems, our results also provide better algorithms for MOT problems that are already known to be tractable: Our algorithms compute solutions which are exact and sparse. (Previous algorithms can do neither.)