PRESS-NEWS.org - Press Release Distribution
PRESS RELEASES DISTRIBUTION

Danish computer scientist has developed a superb algorithm for findin

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:
Danish computer scientist has developed a superb algorithm for findin

ELSE PRESS RELEASES FROM THIS DATE:

MUSC is first in nation to enroll kids in trial of novel MIS-C therapy

MUSC is first in nation to enroll kids in trial of novel MIS-C therapy
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 ...

Helpful behavior during pandemic tied to recognizing common humanity

Helpful behavior during pandemic tied to recognizing common humanity
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 ...

Ancient group once considered nomadic stayed local

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 ...

Bacterial competition in situations of food scarcity prevents survival of mutants

Bacterial competition in situations of food scarcity prevents survival of mutants
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 ...

harp reductions in costs of producing cannabis, fentanyl likely to spur widespread changes in use, dependence

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 ...

New IceCube detection proves 60-year-old theory

New IceCube detection proves 60-year-old theory
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 ...

Study finds lower dose of ketamine equally effective in reducing pain

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 ...

New spherical nucleic acid 'drug' kills tumor cells in humans with glioblastoma

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, ...

Analysis of "virtual" pollinator trade reveals global dependence on biodiversity for food consumption

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, ...

Where am I going? Just ask your subiculum

Where am I going? Just ask your subiculum
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:

New study unveils key strategies against drug-resistant prostate cancer

Northwestern Medicine, West Health, Meadows Mental Health Policy Institute collaboration to provide easier access to mental health care

New method reveals DNA methylation in ancient tissues, unlocking secrets of human evolution

Researchers develop clinically validated, wearable ultrasound patch for continuous blood pressure monitoring

Chromatwist wins innovate UK smart grant for £0.5M project

Unlocking the secrets of the first quasars: how they defy the laws of physics to grow

Study reveals importance of student-teacher relationships in early childhood education

Do abortion policy changes affect young women’s mental health?

Can sown wildflowers compensate for cities’ lack of natural meadows to support pollinating insects?

Is therapeutic hypothermia an effective treatment for hypoxic-ischemic encephalopathy, a type of neurological dysfunction in newborns?

Scientists discover the molecular composition of potentially deadly venomous fish

What are the belowground responses to long-term soil warming among different types of trees?

Do area-wide social and environmental factors affect individuals’ risk of cognitive impairment?

UCLA professor Helen Lavretsky reshapes brain health through integrative medicine research

Astronauts found to process some tasks slower in space, but no signs of permanent cognitive decline

Larger pay increases and better benefits could support teacher retention

Researchers characterize mechanism for regulating orderly zygotic genome activation in early embryos

AI analysis of urine can predict flare up of lung disease a week in advance

New DESI results weigh in on gravity

New DESI data shed light on gravity’s pull in the universe

Boosting WA startups: Report calls for investment in talent, diversity and innovation

New AEM study highlights feasibility of cranial accelerometry device for prehospital detection of large-vessel occlusion stroke

High cardiorespiratory fitness linked to lower risk of dementia

Oral microbiome varies with life stress and mental health symptoms in pregnant women

NFL’s Arizona Cardinals provide 12 schools with CPR resources to improve cardiac emergency outcomes

Northerners, Scots and Irish excel at detecting fake accents to guard against outsiders, Cambridge study suggests

Synchronized movement between robots and humans builds trust, study finds

Global experts make sense of the science shaping public policies worldwide in new International Science Council and Frontiers Policy Labs series

The Wistar Institute and Cameroon researchers reveals HIV latency reversing properties in African plant

$4.5 million Dept. of Education grant to expand mental health services through Binghamton University Community Schools

[Press-News.org] Danish computer scientist has developed a superb algorithm for findin