String Diagram of Optimal Transports
This work addresses hierarchical transportation planning, likely for logistics or data analysis, but appears incremental as it builds on existing OT methods with a novel algebraic composition approach.
The paper tackles hierarchical optimal transport problems by introducing a framework using string diagrams, which reduces them to standard OT problems and enables efficient synthesis of optimal plans, with experimental results showing performance advantages over naive methods.
We present a novel hierarchical framework for optimal transport (OT) using string diagrams, namely string diagrams of optimal transports. This framework reduces complex hierarchical OT problems to standard OT problems, allowing efficient synthesis of optimal hierarchical transportation plans. Our approach uses algebraic compositions of cost matrices to effectively model hierarchical structures. We also study an adversarial situation with multiple choices in the cost matrices, where we present a polynomial-time algorithm for a relaxation of the problem. Experimental results confirm the efficiency and performance advantages of our proposed algorithm over the naive method.