A researcher has advanced the bipartite matching problem in computer science by drawing inspiration from biological processes observed in the nervous system.
In nature, neurons compete to form connections with muscle fibers in a highly efficient manner. Saket Navlakha has adapted this biological mechanism into a streamlined algorithm.
This new approach not only improves the accuracy of pairings, leading to shorter wait times in practical applications like ridesharing, but also enhances privacy by removing the need for centralized data processing.
Rideshare Optimization and Computer Science Challenges
When you request a ride through a rideshare app, the company's computers spring into action. They understand that you want to reach your destination as quickly as possible, that other users also need rides, and that drivers prefer to minimize idle time by picking up nearby passengers.
The computer’s task, according to Cold Spring Harbor Laboratory Associate Professor Saket Navlakha, is to match drivers with riders in a way that maximizes satisfaction for all parties involved.
This task is known as bipartite matching in computer science. It’s the same challenge faced in matching organ donors with recipients, medical students with residency programs, and advertisers with ad slots. Due to its wide-ranging applications, bipartite matching is a subject of significant study.
“This is probably one of the 10 most famous problems in computer science,” says Navlakha.
Biological Insights Applied to Computer Algorithms
Navlakha has now improved the bipartite matching process by drawing on biological principles. He identified a similar problem in the wiring of the nervous system. In adult animals, each muscle fiber is paired with a single neuron that controls its movement.
However, during early development, many neurons initially connect to the same muscle fiber. To enable efficient movement, the nervous system must prune these excess connections. But how does it determine which connections to maintain?
The nervous system has devised an effective solution. Navlakha explains that neurons connected to the same muscle fiber engage in a form of competition, using neurotransmitters as "bidding" resources.
Neurons that lose this biological auction can redirect their resources to bid on other muscle fibers, ensuring that each neuron and muscle fiber ultimately forms a stable pair.
Navlakha adapted this competitive matching strategy into a simple algorithm. “It’s just two equations,” he says. “One governs the competition between neurons connected to the same fiber, and the other handles the reallocation of resources.”
Advantages of a Neuroscience-Inspired Algorithm
When tested against existing bipartite matching algorithms, Navlakha’s neuroscience-inspired approach performed exceptionally well. It generated near-optimal pairings and left fewer participants unmatched. In practical terms, this could translate to shorter wait times for rideshare passengers and better staffing at hospitals.
Privacy and Broader Applications
Another significant advantage of Navlakha’s algorithm is its ability to preserve privacy. Most bipartite matching systems rely on transmitting relevant data to a central server for processing. However, in many scenarios—from online auctions to organ donation matching—a decentralized approach is preferable. With its wide range of potential applications, Navlakha hopes that others will adopt and adapt this new algorithm for their specific needs.
“It’s a prime example of how studying neural circuits can uncover new algorithms for solving important AI challenges,” he concludes.
Published 2 September 2024, Proceedings of the National Academy of Sciences.
DOI: 10.1073/pnas.2321032121
Discover :
