Warm Start Algorithms for Bipartite Matching and Optimal Transport

Minimum Cost Bipartite Matching and Optimal Transport are essential optimization challenges with applications in logistics, artificial intelligence, and multimodal data alignment. These problems involve finding efficient pairings while minimizing costs. Due to the combinatorial nature of minimum-cost bipartite matching and optimal transport problems, the worst-case time complexities of standard algorithms are often prohibitively high. To mitigate this, prior information or warm starts are commonly employed to accelerate computation.

In this thesis, we propose two novel warm-start algorithms for solving the minimum-cost bipartite matching problem, with the first algorithm extending naturally to the optimal transport problem. The first algorithm uses the LMR algorithm to produce dual weights with respect to a scaled version of an approximate matching or transport plan with high additive error. Using these dual weights as warm starts enables a faster computation of approximate matchings or transport plans with extremely small additive error (delta) faster than the original LMR algorithm, which currently holds the state-of-the-art execution time for approximating the optimal transport plan, a generalization of bipartite matching, in the sequential setting.

By achieving lower additive error at a faster rate, our method provides a smoother trade-off between exact and approximate matchings or transport plans. Given that C is the largest cost of the given matching or transportation problem and delta is our chosen additive error, the running time for our first warm start algorithm for matching is O(n^2 * min(C / delta, sqrt(n))) and for optimal transport is O(n^2 * min(sqrt(nC / delta), C / delta)).

Our second warm-start algorithm leverages machine-learned weights to accelerate the computation of minimum-cost bipartite matching. This learning-augmented approach achieves a theoretically superior running time compared to the previous best learning-augmented algorithms for the same problem. Overall, this thesis highlights the effectiveness of combining theoretical algorithmic advancements with modern learning-based techniques, resulting in robust and efficient solutions for fundamental optimization problems.