Most NP-complete problems can be approximated quickly enough for practical purposes.
Decentralized routing is a hard problem, but there has been a lot of research with pretty convincing results. I'm not sure if it scales to the size of the internet, though.
That's the point, though: I don't know if you can find an 'approximate' solution to decentralized routing, since you need precision. Do you have any peer-reviewed articles evidencing these convincing results? I'd be extremely interested in learning some more about this.
Difference in definitions: I read "approximate solution" as an "approximate route," as in the node choices are approximated (potentially leading to a wrong final node, or losing packets at a dead end). Instead, finding approximately the shortest route that doesn't lose packets and gets you to the correct node would presumably work.
Decentralized routing is a hard problem, but there has been a lot of research with pretty convincing results. I'm not sure if it scales to the size of the internet, though.