A researcher has enhanced the bipartite matching problem in computer science by drawing parallels with biological processes in the nervous system.
In nature, neurons compete to connect with muscle fibers, an efficient system Navlakha adapted into a simple algorithm. This new method not only improves pairing accuracy, reducing wait times in real-world applications like ridesharing, but also enhances privacy by eliminating the need for central data processing.
Rideshare Optimization and Computer Science Challenges
When you ask a rideshare app to find you a car, the company’s computers get to work. They know you want to reach your destination quickly. They know you’re not the only user who needs a ride. And they know drivers want to minimize idle time by picking up someone nearby. The computer’s job, says Cold Spring Harbor Laboratory Associate Professor Saket Navlakha, is to pair drivers with riders in a way that maximizes everyone’s happiness.
Computer scientists like Navlakha call this bipartite matching. It’s the same task handled by systems pairing organ donors with transplant candidates, medical students with residency programs, and advertisers with ad slots. As such, it’s the subject of intense study.
“This is probably one of the 10 most famous problems in computer science,” says Navlakha.
Biological Insights Into Computer Algorithms
Now, he’s found a way to do it better by taking a cue from biology. Navlakha recognized a bipartite matching problem in the wiring of the nervous system. In adult animals, each of the body’s muscle fibers is paired with exactly one neuron that controls its movement. However, early in life, every fiber is targeted by many neurons. To get an animal moving efficiently, excess connections must be pruned. So, which matches are made to last?
The nervous system has an efficient solution. Navlakha explains that neurons initially connected to the same muscle fiber compete against each other to maintain their match, using neurotransmitters as “bidding” resources. Neurons that lose this biological auction can take their neurotransmitters and bid on other fibers. This way, every neuron and fiber eventually winds up with a partner.
Navlakha devised a way to implement this matching strategy outside the nervous system. “It’s a simple algorithm,” he says. “It’s only two equations. One is the competition between neurons connected to the same fiber, and two is the reallocation of resources.”
Advantages of a Neuroscience-Inspired Algorithm
Tested against the best bipartite matching programs out there, the neuroscience-inspired algorithm performs very well. It creates near-optimal pairings and leaves fewer parties unmatched. In everyday applications, that could mean shorter wait times for rideshare passengers and fewer hospitals without medical residents.
Privacy and Practical Applications
Navlakha points out another advantage. The new algorithm preserves privacy. Most bipartite matching systems require that pertinent information be relayed to a central server for processing. But in many cases—from online auctions to donor organ matching—a distributed approach may be preferred. With countless potential applications, Navlakha hopes others will adapt the new algorithm for tools of their own.
“It’s a great example of how studying neural circuits can reveal new algorithms for important AI problems,” he adds.
Reference: 2 September 2024, Proceedings of the National Academy of Sciences.
DOI: 10.1073/pnas.2321032121
Funding: Pew Charitable Trusts, National Institute on Deafness and Other Communication Disorders, National Institutes of Health