Danish computer scientist has developed a superb algorithm for findin
2021-03-10
(Press-News.org) One of the most classic algorithmic problems deals with calculating the shortest path between two points. A more complicated variant of the problem is when the route traverses a changing network--whether this be a road network or the internet. For 40 years, an algorithm has been sought to provide an optimal solution to this problem. Now, computer scientist Christian Wulff-Nilsen of the University of Copenhagen and two research colleagues have come up with a recipe.
When heading somewhere new, most of us leave it to computer algorithms to help us find the best route, whether by using a car's GPS, or public transport and map apps on their phone. Still, there are times when a proposed route doesn't quite align with reality. This is because road networks, public transportation networks and other networks aren't static. The best route can suddenly be the slowest, e.g. because a queue has formed due to roadworks or an accident.
People probably don't think about the complicated math behind routing suggestions in these types of situations. The software being used is trying to solve a variant for the classic algorithmic "shortest path" problem, the shortest path in a dynamic network. For 40 years, researchers have been working to find an algorithm that can optimally solve this mathematical conundrum. Now, Christian Wulff-Nilsen of the University of Copenhagen's Department of Computer Science has succeeded in cracking the nut along with 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 prestigious FOCS 2020 conference.
Optimally, in this context, refers to an algorithm that spends as little time and as little computer memory as possible to calculate the best route in a given network.
This is not just true of road and transportation networks, but also the internet or any other type of network.
Networks as graphs
The researchers represent a network as a so-called dynamic graph". In this context, a graph is an abstract representation of a network consisting of edges, roads for example, and nodes, representing intersections, for example. When a graph is dynamic, it means that it can change over time. The new algorithm handles changes consisting of deleted edges--for example, if the equivalent of a stretch of a road suddenly becomes inaccessible due to roadworks.
"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," explains Christian Wulff-Nilsen.
Traditional algorithms assume that a graph is static, which is rarely true in the real world. When these kinds of algorithms are used in a dynamic network, they need to be rerun every time a small change occurs in the graph--which wastes time.
More data necessitates better algorithms
Finding better algorithms is not just useful when travelling. It is necessary in virtually any area where data is produced, as Christian Wulff-Nilsen points out:
"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 hopes that it will be possible to use this algorithm or some of the techniques behind it in practice, but stresses that this is theoretical evidence and first requires experimentation.
INFORMATION:
FACTS:
The research article "Near-Optimal Decremental SSSP in Dense Weighted Digraphs" was presented at the prestigious FOCS 2020 conference.
The article was written by Christian Wulff-Nilsen, of the University of Copenhagen's Department of Computer Science, and former Department of Computer Science PhD student Maximillian Probst Gutenberg and assistant professor Aaron Bernstein of Rutgers University.
The version of the "shortest path" problem that the researchers solved is called "The Decremental Single-Source Shortest Path Problem". It is essentially about maintaining the shortest paths in a changing dynamic network from one starting point to all other nodes in a graph. The changes to a network consist of edge removals.
The paper gives a mathematical proof that the algorithm is essentially the optimal one for dynamic networks. On average, users will be able to change routes according to calculations made in constant time.
[Attachments] See images for this press release:
ELSE PRESS RELEASES FROM THIS DATE:
2021-03-10
A team of pediatricians at the Medical University of South Carolina (MUSC) was the first in the nation to enroll patients with multisystem inflammatory syndrome in children (MIS-C), a rare but life-threatening complication of COVID-19, in a trial of remestemcel-L. This investigational cell therapy, developed and manufactured by Mesoblast, New York, New York, had previously been shown safe and effective for other inflammatory conditions. The MUSC team reports in Pediatrics that the two children enrolled thus far showed significant improvement within 24 hours of remestemcel-L administration.
"While it appears to many people that COVID is no big deal ...
2021-03-10
During the COVID-19 pandemic, people who recognize the connections they share with others are more likely to wear a mask, follow health guidelines and help people, even at a potential cost to themselves, a new University of Washington study shows.
Indeed, an identification with all humanity, as opposed to identification with a geographic area like a country or town, predicts whether someone will engage in "prosocial" behaviors particular to the pandemic, such as donating their own masks to a hospital or coming to the aid of a sick person.
The study, published March 10 in PLOS ONE, is drawn from about 2,500 responses, from more than 80 countries, to an online, international ...
2021-03-10
Images
As far back as the Greek historian Herodotus, a group of people called the Scythians were considered highly mobile warrior nomads.
Scythian-era people lived across Eurasia from about 700 BCE to 200 BCE, and have long been considered highly mobile warriors who ranged widely across the steppe grasslands. Herodotus describes Scythian populations as living in wagons and engaging in raiding and warfare, and this view has persisted throughout history--supported by archeologists' observations of similar styles of horse harnesses, weapons, burial mounds and animal style motifs throughout ...
2021-03-10
A study conducted by researchers at the University of São Paulo in Brazil shows that competition for nutrients and lack of cooperation among bacteria of the species Escherichia coli in the same population and in situations of food scarcity prevent mutants that are better adapted to the environment from flourishing, except those that organize in small groups. The phenomenon masks the emergence of novel bacterial variants, making the mutation rate seem lower than it is in fact.
Mutants constantly emerge and accumulate from one generation to the next. Mutation frequency determines the evolution of a given species. Understanding ...
2021-03-10
The legalization of cannabis and the arrival of nonmedical fentanyl are fundamentally changing drug markets in North America. A large part of these changes relates to the ability to produce large quantities of the drugs at low costs, which has slashed wholesale prices for both drugs and retail prices for cannabis. A new analysis explores the effects of these changes on use. The analysis concludes that sharp declines in production costs for cannabis and opioids could dramatically reduce the price per dose for consumers in ways that alter patterns of use and dependence.
The analysis, by a researcher at Carnegie Mellon University (CMU), is published in the International Journal of Drug Policy.
"Historical analogies suggest that very large ...
2021-03-10
On December 6, 2016, a high-energy particle called an electron antineutrino was hurtling through space at nearly the speed of light. Normally, the ghostly particle would zip right through the Earth as if it weren't even there.
But this particle just so happened to smash into an electron deep inside the South Pole's glacial ice. The collision created a new particle, known as the W- boson. That boson quickly decayed, creating a shower of secondary particles.
The whole thing played out in front of the watchful detectors of a massive telescope buried in the Antarctic ice, the IceCube Neutrino Observatory. This enabled IceCube ...
2021-03-10
MAYWOOD, IL - A recent Loyola Medicine study found that reducing the standard dose of IV-administered ketamine in half is as effective as the larger, standard dose in reducing pain in adults.
Ketamine is known to provide pain relief comparable to opioid medications, which are highly addictive. In the recent study, appearing in the journal Academic Emergency Medicine, researchers studied 98 patients, ages 18 to 59, who presented to the emergency department with acute, moderate to severe pain. The patients were randomized prospectively to receive either 0.15 mg/kg of ketamine (low dose) or 0.30 mg/kg (high dose). Patients ...
2021-03-10
Drug developed by Northwestern scientists
Fatal brain cancer has no current cure
Drug is revolutionary new class of drugs applicable to other neurological diseases
CHICAGO --- An early clinical trial in individuals with the deadly brain cancer, glioblastoma, showed an experimental spherical nucleic acid (SNA) drug developed by Northwestern University scientists was able to penetrate the blood-brain barrier and trigger the death of tumor cells.
This is the first time a nanotherapeutic has been shown to cross the blood-brain barrier when given through intravenous infusion and alter the genetic machinery of a tumor to cause cell death. The drug crossed the blood-brain barrier, ...
2021-03-10
By analyzing more than a decade's worth of information on 55 crops, all dependent on pollinators, scientists have revealed that developed countries are particularly reliant on imported pollinator-dependent crops, while countries that export the majority of these crop types are major drivers of pollinator declines. Their assessment of the "virtual" exchange of pollinator services in the global food trade could help governments and agencies form new policies to preserve crop diversity and tackle biodiversity loss. In today's globalized world, human food consumption largely depends on the trade of crops and the intense use of resources such as water and land. Pollinators such as bees, ...
2021-03-10
OSAKA, Japan - The hippocampus is the part of the brain that deals with information associated with spatial navigation and memory. For example, you are driving and despite the changing environment of different cars going at varying speeds, on and off ramps, distracting billboards, etc., you adjust your speed, glance only momentarily at the billboards, and navigate the roads in a smooth and timely manner. This is your hippocampus at work. It takes the input - a continuously changing environment - and helps turn it into the output - using memory of a road map to safely navigate your way. However, little is known about how information is distributed from the hippocampus to other brain regions that results in the output behaviour.
A research team led by Lecturer Takuma Kitanishi and Professor ...
LAST 30 PRESS RELEASES:
[Press-News.org] Danish computer scientist has developed a superb algorithm for findin
