Warm Start Algorithms for Bipartite Matching and Optimal Transport
| dc.contributor.author | Mittal, Akash | en |
| dc.contributor.committeechair | Ji, Bo | en |
| dc.contributor.committeechair | Raghvendra, Sharath | en |
| dc.contributor.committeemember | Hoang, Thang | en |
| dc.contributor.department | Computer Science and#38; Applications | en |
| dc.date.accessioned | 2025-01-23T09:00:48Z | |
| dc.date.available | 2025-01-23T09:00:48Z | |
| dc.date.issued | 2025-01-22 | |
| dc.description.abstract | 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. | en |
| dc.description.abstractgeneral | Matching problems and optimal transport are foundational tools with wide-ranging applications in fields like logistics, artificial intelligence, and multimodal data analysis. At their core, these problems involve finding the most efficient way to pair objects or resources while minimizing associated costs. Imagine we are tasked with pairing items from two groups based on compatibility. A perfect matching ensures every item is paired exactly once, maximizing compatibility. Often, the challenge extends to minimizing the cost of these matchings, resulting in the minimum-cost maximum-cardinality matching problem. This problem is fundamental to both theoretical algorithmic research and real-world applications like resource allocation, task scheduling, and network optimization. Optimal transport builds on this idea, where we align resources (e.g., supply nodes) with demands (e.g., demand nodes) in a way that minimizes transportation costs. For instance, consider distributing supplies across a network with varying transport costs. The goal is to fully meet demands while minimizing the overall cost—a crucial requirement in supply chain logistics, training generative models like GANs, and aligning multimodal data such as text and images. This research introduces warm start algorithms to accelerate these complex problems by leveraging two strategies: 1. Machine Learning for Dual Weights: Predictive models are used to estimate dual weights that guide optimization, reducing the computational complexity of solving the problem. 2. Simplified Problem Refinements: Initial solutions are derived from solving simplified sub-problems, which are then iteratively refined for improved precision and efficiency.By combining algorithmic rigor with predictive and incremental approaches, these methods scale efficiently to large datasets and diverse applications. This work not only advances the theoretical understanding of optimization problems but also can have practical impacts in areas like generative modeling and cross-modal alignment. | en |
| dc.description.degree | Master of Science | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:42438 | en |
| dc.identifier.uri | https://hdl.handle.net/10919/124319 | |
| dc.language.iso | en | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | Optimal Transport | en |
| dc.subject | Bipartite Matching | en |
| dc.subject | Primal-Dual Method | en |
| dc.subject | Learning Augmented Algorithms | en |
| dc.subject | Additive Approximation Algorithms | en |
| dc.title | Warm Start Algorithms for Bipartite Matching and Optimal Transport | en |
| dc.type | Thesis | en |
| thesis.degree.discipline | Computer Science & Applications | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | masters | en |
| thesis.degree.name | Master of Science | en |
Files
Original bundle
1 - 1 of 1