Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: