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. Navlakha says:
"This is probably one of the 10 most famous problems in computer science."
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."
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.
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.
About Cold Spring Harbor Laboratory:
Founded in 1890, Cold Spring Harbor Laboratory has shaped contemporary biomedical research and education with programs in cancer, neuroscience, plant biology and quantitative biology. Home to eight Nobel Prize winners, the private, not-for-profit Laboratory employs 1,000 people including 600 scientists, students and technicians.
For more information, visit www.cshl.edu
