Shot of an unidentifiable businesswoman using her car’s built-in GPS while driving
Computer algorithms are quite useful in finding the best route to a destination, whether through a car’s GPS or public transport and maps apps. There are some times however when the proposed route doesn’t align with reality. This is because road networks are dynamic. The best route may suddenly become the slowest because of a queue or an accident.
The software being used in situations like these is attempting to solve a variant for the classic algorithmic ‘shortest path’ problem. For the past four decades, researchers have been working on finding an algorithm to optimally solve this mathematical conundrum. Now, Christian Wulff-Nilsen of the University of Copenhagen’s Department of Computer Science has resolved this issue with his two colleagues.
‘We have developed an algorithm, for which we now have mathematical proof, that it is better than every other algorithm up to now— and the closest thing to optimal that will ever be, even if we look 1000 years into the future’, says Associate Professor Wulff-Nilsen. The results were presented at the FOCS 2020 Conference.
‘Optimally’ here refers to an algorithm which uses the least time and computer memory to calculate the best route in a network. It works with the road and transportation networks, as well as the internet and any other type of network.
The researchers presented a network as a ‘dynamic graph’. A graph here is an abstract representation of network with edges or roads, and nodes. A graph is dynamic when it changes over time. The novel algorithm handles changes of deleted edges.
‘The tremendous advantage of seeing a network as an abstract graph is that it can be used to represent any type of network. It could be the internet, where you want to send data via as short a route as possible, a human brain or the network of friendship relations on Facebook. This makes graph algorithms applicable in a wide variety of contexts’, says Wulff-Nilsen.
Traditional algorithms presume that a graph is static which is rarely true in the real world. When they are used in a dynamic network, they have to be rerun when a small change occurs in the graph, which is time wasting.
Finding more effective algorithms is useful for any area where data is produced.
‘We are living in a time when volumes of data grow at a tremendous rate and the development of hardware simply can’t keep up. In order to manage all of the data we produce, we need to develop smarter software that requires less running time and memory. That’s why we need smarter algorithms’, he says.
He has high hopes that the algorithm will be useful in practice, but emphasizes that it is only theoretical evidence for now and requires testing.
By Marvellous Iwendi.
Source: UOC