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.
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.
I 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.
Maximum flow isn't NP-hard, though. It can be solved in near-linear time.
Mostly as a subproblem solver for mixed-integer programs, due to ease of warm-start. MIP itself is NP (B&B), so NP*NP=NP