37 ms·
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 resea
by joelthelion 15y ago
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.
- law 15y agoThat'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.
- pyre 15y agoWho is the current centralized authority that figures out the shortest routes today?
- law 15y agoDifference 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.