Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.
I have formally dealt with approximation algorithms before and I skimmed the wikipedia article, yet I did not find anything that contradicts me. Note the in the section on hardness, P and NP (obviously) appear as bounds of solutions. Where is the contradiction?
Further, all this (approximation algos and P/NP algos) are discrete, complete algorithms. ML is a completely different story, as one is never certain whether some optimum is global or local. Hence, ML is a heuristic, while Djikstras shortest path algorithm is a series of steps with a success guarantee (with provable worst runtime behavior).
The paper proves that Tetris is NP hard, but that is only because Tetris is infinitely long game. It's still easy for a computer to play as well as a human and faster