Unifying strongly polynomial algorithms for subclasses of Linear Programs

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


Duration: 11:06
149 views
4

Bento Natura (Georgia Tech)
https://simons.berkeley.edu/talks/bento-natura-georgia-tech-2023-09-08
Meet the Fellows Welcome Event Fall 2023

The existence of a strongly polynomial algorithm for linear programs (LP) is one of the most important open problems in theoretical computer science. The last decades have seen tremendous progress for special subclasses of LP (e.g., minimum cost flow, multi-commodity flow, discounted Markov decision processes) whose proofs of strong polynomiality rely on very different ideas, algorithms and techniques. Together with Allamigeon, Dadush, Loho, and Végh (FOCS 2022) we devised an interior point method that runs in strongly polynomial time whenever a certain curvature is polynomially bounded. Taking this algorithm as a blackbox, we show how strong polynomiality for many of the subclasses of LP can be recovered.



Other Videos By Simons Institute for the Theory of Computing


2023-09-08Massively Parallel Join Algorithms
2023-09-08Relational Programming
2023-09-08Title: Research Interests and Latest Works
2023-09-08What can the demand analyst learn from machine learning?
2023-09-08From Robustness to Privacy and Back
2023-09-08Decoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
2023-09-08Risk Convergence and Algorithmic Regularization of Discrete-Stepsize (Stochastic) Gradient Descent
2023-09-08Quantum Cryptography in Algorithmica
2023-09-08Noncommutative constraint satisfaction problems
2023-09-08Faster inverse maintenance for faster conic programming
2023-09-08Unifying strongly polynomial algorithms for subclasses of Linear Programs
2023-09-08Fast sparsification via convex optimization and chaining
2023-09-08Practical Graph Algorithms: Scalability and Privacy
2023-09-08Recent advances in vertex connectivity
2023-09-08Shortest paths, dynamic algorithms, and fine-grained complexity
2023-09-08Recent Trends in Minimum Cut Algorithms
2023-09-05Introduction to Data Structures and Optimization for Fast Algorithms
2023-09-01Optimization: Interior Point Methods Part 2
2023-09-01Optimization: Interior Point Methods Part 1
2023-09-01Matrix Data Structures
2023-08-31Optimization: Higher-order Methods Part 2


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Meet the Fellows Welcome Event Fall 2023
Bento Natura