3 ms·
Perfect example is the simplex algorithm. We do have a polynomial algorithm for linear programming yet simplex (with exponential worst case performance) is our
by whatever1 2mo ago
Perfect example is the simplex algorithm.
We do have a polynomial algorithm for linear programming yet simplex (with exponential worst case performance) is our tool of choice.
- senshan 2mo agoMostly as a subproblem solver for mixed-integer programs, due to ease of warm-start. MIP itself is NP (B&B), so NP*NP=NP
- mjd 2mo agoI was surprised that Gruhn didn't include this in his list of problems where the NP-hardness is not that important in practice. I think the Ford-Fulkerson maximum flow algorithm may be another example.
- JohnKemeny 2mo agoMaximum flow isn't NP-hard, though. It can be solved in near-linear time.