Combinatorial Optimization Courses and Certifications

Simons Institute

Utilizing Structure in Combinatorial Solving and Reasoning

Efficient utilization of structure for combinatorial problem solving, focusing on treewidth measure and answer set programming. Explores runtime bounds, decomposition-guided reductions, and empirical results in hard reasoning modes.

• YouTube
• 40 minutes
• On-Demand
• Free Video

Simons Institute

Minimum Isolating Cuts - A New Tool for Solving Minimum Cut Problems

Explore a powerful new tool for solving minimum cut problems in combinatorial optimization, with applications to global, Steiner, and all-pairs min-cut algorithms.

• YouTube
• 41 minutes
• On-Demand
• Free Video

Institute for Pure & Applied Mathematics (IPAM)

Decision-Focused Learning - Integrating Downstream Combinatorics in ML

Explore the integration of machine learning and discrete optimization to enhance problem-solving in real-world scenarios, focusing on decision-focused learning and tailored solution strategies.

• YouTube
• 27 minutes
• On-Demand
• Free Video

Institute for Pure & Applied Mathematics (IPAM)

Structured ML Training via Conditional Gradients

Explore conditional gradient methods for structured optimization in machine learning, covering applications in traditional and deep learning, with a focus on incorporating polyhedral structures into solutions.

• YouTube
• 24 minutes
• On-Demand
• Free Video

Institute for Pure & Applied Mathematics (IPAM)

How Much Data Is Sufficient to Learn High-Performing Algorithms?

Explore data-driven algorithm design's impact on performance, focusing on generalization guarantees for combinatorial algorithms with piecewise-structured parameter functions.

• YouTube
• 25 minutes
• On-Demand
• Free Video

Institute for Pure & Applied Mathematics (IPAM)

A Framework for Differentiable Discovery of Graph Algorithms

Explore graph algorithm discovery using deep learning and tree decomposition. Learn effective techniques for NP-complete problems with interpretable results and expanded search space.

• YouTube
• 29 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Neil Olver: On the Integrality Gap of the Prize Collecting Steiner Forest LP

Explores the integrality gap of the prize collecting Steiner forest LP, disproving the belief it was 2 and showing it's at least 9/4, with implications for approximation algorithms in combinatorial optimization.

• YouTube
• 28 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Viswanath Nagarajan - Stochastic Load Balancing on Unrelated Machines

Explores stochastic load balancing on unrelated machines, presenting a constant factor approximation algorithm for minimizing expected makespan. Discusses LP relaxation and rounding techniques.

• YouTube
• 32 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Finding Perfect Matchings in Bipartite Hypergraphs

Explore efficient algorithms for finding perfect matchings in bipartite hypergraphs, extending Haxell's condition and the Hungarian algorithm to hypergraph structures.

• YouTube
• 29 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Louis Theran: Rigidity of Random Graphs in Higher Dimensions

Explore rigidity properties of random graphs in higher dimensions and their connection to matrix completion, with insights on thresholds and optimal conditions.

• YouTube
• 32 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Recent Results on Maximizing Submodular Functions

Explore recent advancements in submodular maximization, covering constrained and unconstrained scenarios for monotone and non-monotone functions within combinatorial optimization.

• YouTube
• 1 hour 6 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Provable Submodular Function Minimization via Fujishige Wolfe Algorithm

Explore submodular function minimization through the Fujishige-Wolfe algorithm, analyzing its convergence and implications for combinatorial optimization.

• YouTube
• 25 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Maximizing Monotone Submodular Functions over the Integer Lattice

Explore advanced algorithms for maximizing monotone submodular functions on integer lattices, with applications in machine learning and combinatorial optimization.

• YouTube
• 30 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Reassembling Trees for the Traveling Salesman

Explore advanced approximation algorithms for traveling salesman problems, focusing on tree reassembly techniques to improve solutions beyond traditional methods.

• YouTube
• 31 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

On Element Connectivity Preserving Graph Simplification

Explores element-connectivity in graph simplification, focusing on reduction techniques, algorithmic results, and applications in network design. Highlights open problems and submodularity properties for faster algorithms.

• YouTube
• 46 minutes
• On-Demand
• Free Video