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. / Master of Science / 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.

<p dir="ltr">Machine learning has revolutionized the field of computer science in the recent years, yet its lack of rigorous, worst-case guarantees has raised various theoretical and practical concerns. The computer science community have thus shifted focus to <i>data-dependent</i> algorithm design and analysis, approaching the given algorithm problem with the specific instance in perspective, that can often times provide more fine-grained guarantees that better capture the non-worst-case patterns in real-world input that machine learning relies on. This thesis examines two classical problems from a data-dependent perspective: (1) Online optimization of covering and packing programs, augmented with untrusted predictions, and (2) instance-by-instance bounds on the hardness of mean estimation on the real line, accompanied by a novel beyond worst-case definition of optimality.</p><p dir="ltr">In the first part, we study <i>learning-augmented algorithms</i> in the context of online convex covering and concave packing optimization, utilizing untrusted data-dependent advice prudently to outperform classical counterparts reliably. We propose general-purpose frameworks for linear covering and concave packing, based on the simple idea of switching between candidate solutions from either the prediction or any classical online algorithm as a black-box subroutine. For convex covering where the switching strategy does not work, we extend the celebrated primal-dual framework, fine-tuning it to incorporate the external predictions. We show that our algorithmic frameworks beat classical impossibility results when the advice is accurate, while able to maintain robustness even if the advice is arbitrarily misleading.</p><p dir="ltr">In the second part, we examine the classical one-dimensional mean estimation problem, investigating whether it is possible to further our understanding of the estimation error landscape, beyond the worst-case sub-Gaussian rate. Our analyses show that in general the sub-Gaussian rate is in fact optimal on an instance-by-instance basis, and can only be outperformed if we make additional assumptions about the underlying distribution, such as symmetry. We formalize this notion of data-dependent optimality as <i>neighborhood optimality</i>, and provide tools to analyze estimators under this novel framework, establishing connections to robust mean estimation.</p>