See notes on:

  • Mathematical Programming

Polynomial Time Problems

There are some problems that a tractable. It’s bizarre. Many of them are reducible to linear programming.

Dynamic Programming

Sometimes these are cheating in a sense. But if it works it works

Shortest Path

https://en.wikipedia.org/wiki/Shortest_path_problem

Network Flow

https://en.wikipedia.org/wiki/Flow_network

Matroid

Constraint Satisfaction Problems

Travelling Salesman

Approximation Algorithms

Relaxations

https://opensource.googleblog.com/2022/02/A-New-Library-for-Network-Optimization.html