Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,800
Published on ● Video Link: https://www.youtube.com/watch?v=HfoJFOe1oaY


Duration: 1:00:19
937 views
18

Bento Natura (UC Berkeley & Georgia Tech)
https://simons.berkeley.edu/talks/bento-natura-uc-berkeley-georgia-tech-2023-11-30
Optimization and Algorithm Design

Recent years have seen tremendous progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow and general Linear Programs (LP). Progress on strongly polynomial solvers for combinatorial LP on the other hand has stalled. For combinatorial LP beyond directed graphs this gap between exact and high-accuracy solvers is currently quadratic. We finally break the quadratic gap and design a strongly polynomial interior-point-method for combinatorial LP, which reduces the gap to only a linear factor.



Other Videos By Simons Institute for the Theory of Computing


2024-02-01Quantum LDPC Codes I
2024-02-01Recent Advances in Multiplicity Codes
2024-02-01Intro to Quantum Codes
2024-02-01Algebraic Codes/Algorithms I
2023-12-08Data Structures and Optimization for Fast Algorithms
2023-12-02Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
2023-12-01Network Unreliability in Sub-quadratic Time
2023-12-01Recent Progress on Submodular Function Minimization
2023-12-01Quotient Sparsification for Submodular Functions
2023-12-01Discrepancy Minimization via Regularization
2023-12-01Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs
2023-11-30Sparsifying Generalized Linear Models
2023-11-30Instance Optimal Iterative Methods for Matrix Function Approximation
2023-11-29Nash Social Welfare and A Tale of Mathematical Programs
2023-11-29Robust Gradient Descent: Agnostically Estimating an Unknown Affine Transformation...
2023-11-28Hitting the High-D(imensional) Notes: An ODE for SGD learning dynamics in high-dimensions
2023-11-27Exploiting geometric structure in (matrix-valued) optimization
2023-11-21Towards Interpretable Data Science
2023-11-13Introduction and Program Highlights
2023-11-13Modern Paradigms in Generalization
2023-11-13Challenges in Research on Practical Algorithms


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Optimization and Algorithm Design
Bento Natura